Làm cách nào để tính toán độ phức tạp về thời gian của thuật toán đệ quy?Độ phức tạp về thời gian của thuật toán đệ quy
int pow1(int x,int n) {
if(n==0){
return 1;
}
else{
return x * pow1(x, n-1);
}
}
int pow2(int x,int n) {
if(n==0){
return 1;
}
else if(n&1){
int p = pow2(x, (n-1)/2)
return x * p * p;
}
else {
int p = pow2(x, n/2)
return p * p;
}
}
Phân tích chức năng đệ quy (hoặc thậm chí đánh giá họ) là một nhiệm vụ không tầm thường. A (theo ý kiến của tôi) giới thiệu tốt có thể được tìm thấy trong Don Knuths Concrete Mathematics.
Tuy nhiên, hãy phân tích các ví dụ này ngay bây giờ:
Chúng tôi xác định hàm cho chúng ta thời gian cần thiết bởi hàm. Giả sử rằng t(n) biểu thị thời gian cần thiết cho pow(x,n), tức là chức năng của n.
Sau đó chúng ta có thể kết luận, rằng t(0)=c, bởi vì nếu chúng ta gọi là pow(x,0), chúng ta phải kiểm tra xem (n==0), và sau đó trở về 1, có thể được thực hiện trong thời gian liên tục (do đó hằng c).
Bây giờ, chúng tôi xem xét trường hợp khác: n>0. Ở đây chúng tôi có được t(n) = d + t(n-1). Đó là bởi vì chúng tôi lại kiểm tra n==1, tính , do đó (t(n-1)) và nhân kết quả theo số x.Kiểm tra và nhân có thể được thực hiện trong thời gian không đổi (hằng số d), phép tính đệ quy của pow cần t(n-1).
Bây giờ chúng ta có thể "mở rộng" thuật ngữ t(n):
t(n) =
d + t(n-1) =
d + (d + t(n-2)) =
d + d + t(n-2) =
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c
Vì vậy, làm thế nào lâu cho đến khi chúng ta đạt t(1)? Kể từ khi chúng tôi bắt đầu tại t(n) và chúng tôi trừ đi 1 trong mỗi bước, phải mất n-1 các bước để đạt được t(n-(n-1)) = t(1). Mặt khác, điều đó có nghĩa là chúng tôi nhận được n-1 lần hằng số d và t(1) được đánh giá là c.
Vì vậy, chúng tôi có được:
t(n) =
...
d + d + d + ... + c =
(n-1) * d + c
Vì vậy, chúng tôi nhận được rằng t(n)=(n-1) * d + c đó là yếu tố O (n).
pow2 có thể được thực hiện bằng cách sử dụng Masters theorem. Vì chúng ta có thể giả định rằng các hàm thời gian cho các thuật toán tăng lên một cách đơn điệu. Vì vậy, bây giờ chúng tôi có thời gian t(n) cần thiết cho việc tính toán pow2(x,n):
t(0) = c (since constant time needed for computation of pow(x,0))
cho n>0 chúng tôi nhận
/t((n-1)/2) + d if n is odd (d is constant cost)
t(n) = <
\ t(n/2) + d if n is even (d is constant cost)
Trên đây có thể được "đơn giản hóa" tới:
t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)
Vì vậy, chúng tôi có được t(n) <= t(n/2) + d, có thể được giải quyết bằng cách sử dụng định lý chủ để t(n) = O(log n) (xem phần Ứng dụng để Popul ar Thuật toán trong liên kết wikipedia, ví dụ "Tìm kiếm nhị phân").
Có thể hơi phức tạp, nhưng tôi nghĩ cách thông thường là sử dụng Master's theorem.
phức tạp của cả hai chức năng bỏ qua đệ quy là O (1)
Đối với pow1 thuật toán đầu tiên (x, n) sự phức tạp là O (n) vì độ sâu của đệ quy tương quan với n tuyến tính.
Đối với độ phức tạp thứ hai là O (log n). Ở đây chúng tôi recurse khoảng log2 (n) lần. Ném ra 2 chúng tôi nhận được đăng nhập n.
Vì vậy, tôi đoán bạn đang tăng x thành lũy thừa n. pow1 lấy O (n).
Bạn không bao giờ thay đổi giá trị của x nhưng bạn lấy 1 từ n mỗi lần cho đến khi nó được 1 (và sau đó bạn chỉ trở lại) Điều này có nghĩa là bạn sẽ thực hiện cuộc gọi đệ quy n lần.
Hãy bắt đầu với pow1, vì đó là cách đơn giản nhất.
Bạn có một chức năng trong đó một lần chạy được thực hiện trong O (1). (Kiểm tra tình trạng, quay trở lại và nhân là thời gian không đổi.)
Những gì bạn còn lại sau đó là đệ quy của bạn. Những gì bạn cần làm là phân tích tần suất hàm sẽ tự gọi. Trong pow1, nó sẽ xảy ra N lần. N * O (1) = O (N).
Đối với pow2, nguyên tắc tương tự - một lần chạy hàm chạy trong O (1). Tuy nhiên, lần này bạn sẽ giảm N mỗi lần. Điều đó có nghĩa là nó sẽ chạy log2 (N) lần - hiệu quả một lần cho mỗi bit. log2 (N) * O (1) = O (log (N)).
Something mà có thể giúp bạn là khai thác thực tế là đệ quy luôn có thể được diễn tả như lặp (không phải lúc nào rất đơn giản, nhưng nó có thể. Chúng tôi có thể bày tỏ pow1 như
result = 1;
while(n != 0)
{
result = result*n;
n = n - 1;
}
Bây giờ bạn có một thuật toán lặp thay vào đó, và bạn có thể tìm thấy nó dễ dàng hơn để phân tích nó như vậy.
Liên kết này cung cấp câu trả lời chính xác cho vấn đề của bạn. Đây là nguồn (http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/recursion12.pdf)
* Độ phức tạp của cả hai hàm là O (1) * - Cái gì? – kennytm
Đó là O (1) bỏ qua các cuộc gọi đệ quy nhưng có thể được thể hiện khác nhau. Vấn đề là tổng độ phức tạp phụ thuộc hoàn toàn vào độ sâu đệ quy. – fgb