Tính toán big O cho hàm đệ quy

Tính toán big O cho hàm đệ quy

Nếu bạn chưa hiểu big O là gì, hãy đọc bài trước: https://8techblog.blogspot.com/2020/05/tim-hieu-o-phuc-tap-thoi-gian-big-o-cho.html

Việc tính toán big O là một việc làm cần thiết trong quá trình lập trình, đặc biệt là với thời buổi hiện nay, kích thước dữ liệu ngày càng lớn và phức tạp, ta cần phải lựa chọn thuật toán và viết code một cách thông minh để đạt hiệu quả. Trong bài viết trước thì mình đã giải thích cách tìm big O rồi phải không nhỉ? Tuy nhiên, đó chỉ là big O cho các lệnh code bình thường. Bạn đang tự hỏi mình lệnh “không bình thường” mình muốn nhắc đến ở đây là gì phải không? Mình nghĩ bạn cũng đã tự trả lời được cho mình khi đọc tiêu đề rồi đấy. Vâng, đó chính là đệ quy. Thật sự khó khi tính toán big O cho các hàm đệ quy, vì việc mà kiểm soát được số lần lặp lại của hàm là chuyện quá ư là khó khăn.

Tất nhiên, phải có giải pháp thì mình mới viết bài này chứ nhỉ :D. Đúng rồi đấy, giải pháp này có thể giúp bạn tính được big O của một hàm đệ quy (đối với từng bài đệ quy cụ thể thì cách giải sẽ khác nhau, nhưng nhìn chung là cùng một dạng). Ở đây mình sẽ đưa ra hai bài toán và tính toán big O cho hai bài đó

Bài toán 1:  Tính tổng các số từ 1 đến n sử dụng hàm đệ quy

Đây chính là hàm tính tổng từ 1 đến n viết theo đệ quy đây. Bây giờ ta định nghĩa T(n) như một hàm số của đồ thị có trục x là n và y là thời gian.

Trục màu đỏ mình vẽ đang mô tả lại  với big O là O(n), hay T(n) = a*x + b. Cái này chỉ để nhắc lại một chút xíu kiến thức cũ thôi nghen :D.

Ta đã đặt T(n) là đồ thị hàm số của hàm đệ quy trên, giờ ta xét 2 tính chất của T(n):

-        Với n = 1, thì T(n) = z₁ , trong đó z₁ là một hằng số bất kỳ thể hiện thời gian thực hiện cho câu lệnh (1) là z₁ giây. Nó là một hằng số vì số bước để thực hiện câu lệnh (1) không thay đổi dù bạn có tăng n.

o   Bạn có thể hiểu câu lệnh này luôn chạy trong thời gian là z₁ giây với mọi input.

-        Với n > 1, thì hàm sẽ thực hiện z₂ giây (z₂ này bao gồm việc gọi n và phép toán cộng - với số lượng các bước để thực hiện câu lệnh không đổi dù tăng n lên)

thêm vào đó là hàm đệ quy sumFromOneToN(n-1) với T(n-1) chỉ lệnh. Tóm lại trong trường hợp này, T(n) = z₂ + T(n-1)

Trước khi đi vào tính toán, ta nên tối giản các hằng số z₁ và z₂ là 1. Vì sao ư?

-        Vì cái chúng ta cần tính là big O, là khả năng phát triển của đồ thị (phát triển theo tuyến tính, theo hàm mũ,...), nghĩa là xem xét mức độ biến thiên của thời gian trên dữ liệu nhận vào ấy. y = a*x + b đổi thành y = x có thay đổi hàm tuyến tính thành hàm khác không? Không. y = b*x² và y = a*x² có thay đổi hàm mũ không? Không. Chính vì thế hằng số không quan trọng khi tính toán big O

-        Nhưng trong hàm T(n) = z₂ + T(n-1) (n>1) mình không thể đặt z₂ bằng 0 được, vì hàm này vẫn chưa xét big O, nó chỉ đang trong giai đoạn xác định từng thành phần. Chúng ta cần phải có hằng số thể hiện để tính toán (nếu z₂ = 0 sẽ loại bỏ mất hằng số). Một ví dụ đơn giản:

o   (n+1)*(1/n) khi tính toán ra thì sẽ là n^-1, và big O sẽ là O(n^-1) (mình không chắc tồn tại big O này không haha)

o   n*(1/n) (đã lược bớt +1) khi tính toán ra sẽ là 1, và big O sẽ là O(1)

ð Ở đây bạn có thể rút ra kết luận nhỏ: Trong giai đoạn xác định từng thành phần, ta có thể thay đổi hằng số tùy thích, trừ số 0 (vì có thể loại bỏ hằng số, gây sai lệch tính toán)

-        Lựa chọn z₁ và z₂ bằng 1 để đơn giản hóa vấn đề! (Bạn có thể để nguyên z₁ và z₂ nếu muốn)

Okay, giờ đi vào vấn đề nào. Ta có:

T(n) = 1 (n = 1) (*)

T(n) = 1 + T(n-1) (**) (n > 1)

Áp dụng (**) vào T(n-1) với n được xem như là n – 1

T(n) = 1 + (1 + T(n-2)) = 2 + T(n-2)

Tiếp tục như thế

T(n) = 2 + T(n – 2) = 2 + (1 + T(n – 3)) = 3 + T(n – 3)

T(n) = 4 + T(n – 4)

T(n) = 5 + T(n – 5)

...

T(n) = k + T(n – k)

Để rút gọn được T(n-k), ta cần biến đổi T(n-k) = T(1), khi đó dựa vào (*) ta sẽ khử được

Để T(n-k) = T(1) thì n – k = 1 => k = n - 1

Khi đó

T(n) = n – 1 + T(1)

T(n) = n – 1 + 1

T(n) = n

Với T(n) = n thì suy ra big O là O(n)

Phương pháp bạn vừa tiếp cận chính là phương pháp tính big O cho hàm đệ quy thông qua tính hàm số.

Bài toán 2: Tính dãy số Fibonacci sử dụng hàm đệ quy

Ở dãy số này ta có thể sử dụng cách tính hàm số để tính big O, nhưng sẽ có một chút phức tạp. Mình sẽ bớt giải thích hơn vì bạn cũng đã quen rồi.

(1)  => T(n) = 1 (n <= 1) (*)

(2)  => T(n) = T(n – 1) + T(n – 2) + 1 (n>1) (**)

Phép toán cộng cũng tốn một khoảng thời gian k nào đó, nên đó là lý do hằng số 1 được cộng vào (**)

Ta thử vẽ đồ thị cho hàm Fibonacci F(n) với n = 4

Ta thấy với F(3) thì thời gian chạy lâu hơn F(2) => T(n-1) > T(n-2)

Để dễ dàng tính toán, ta cho phép xấp xỉ T(n – 1) = T(n – 2) và tính hai big O tương ứng với hai miền giá trị

Miền giá trị dưới:  Chọn T(n – 2)

(**) T(n) = T(n – 1) + T(n – 2) + 1 = 2*T(n – 2) + 1

( T(n – 2) = T(n – 3) + T(n – 4) + 1 = 2*T(n – 4) + 1  )

 T(n) = 2*(2*T(n – 4) + 1) + 1 = 4*T(n – 4) + 3      (k = 2)

T(n) = 4*(2*T(n – 6) + 1) + 3 = 8*T(n – 6) + 7 (k = 3)

T(n) = 8*(2*T(n – 8) + 1) + 7 = 16*T(n – 8) + 15  (k = 4)

...

T(n) = 2^k*T(n – 2*k) + 2^k - 1 (next)

Để T(n – 2*k) = T(0) thì n – 2*k = 0 => n = 2*k => k = n/2

(next) => T(n) = 2^n/2*T(0) + 2^(n/2) – 1 = 2^n/2 +2^n/2 – 1 = 2*2^n/2 – 1

Vậy big O của T(n) đối với cận dưới là O(2^n/2) 

Miền giá trị trên: Chọn T(n – 1)

(**)T(n) = T(n – 1) + T(n – 2) + 1 = 2*T(n – 1) + 1

( T(n – 1) = T(n – 2) + T(n – 3) + 1 = 2*T(n – 2) + 1 )   

T(n) = 2*(2*T(n – 2) + 1) + 1 = 4*T(n – 2) + 3 (k = 2)

T(n) = 4*(2*T(n – 3) + 1) + 3 = 8*T(n – 3) + 7 (k = 3)

...

T(n) =   2^k*T(n – k) + 2^k - 1 (next)

Để T(n – k) = T(0) thì n – k = 0 => k = n

(next) => T(n) = 2ⁿ*T(0) + 2ⁿ – 1 = 2ⁿ +2ⁿ – 1 = 2*2ⁿ – 1

Vậy big O của T(n) đối với cận trên là O(2ⁿ)

Vậy big O của T(n) nằm trong khoảng O(2^n/2) đến O(2ⁿ) (Thông thường người ta sẽ xem xét hàm này với O(2ⁿ)) 

Tổng kết: Vậy là chúng ta đã tìm hiểu được cách tính toán big O cho hàm đệ quy rồi. Một số hàm đệ quy tính toán dễ, nhưng một số thì khá khó. Nếu có thể giải quyết bài toán dưới dạng không đệ quy thì mình nên xem xét, để dễ dàng kiểm tra big O cũng như kiểm soát code của mình.

Cảm ơn các bạn đã đón xem!

Nội dung bài viết thuộc về Lê Công Diễn.

Người viết: Lê Công Diễn

Mang đi nhớ ghi nguồn (nhớ trích link blog người ta nha)