遞歸算法的時間複雜度

Question

如何計算遞歸算法的時間複雜度？

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; 
    } 
} 

Answer 1

分析遞歸函數（或者甚至是評估它們）是一個平凡的任務。A（在我看來）很好的介紹可以在唐Knuths找到Concrete Mathematics。

但是，現在我們來分析這些示例：

我們定義了一個函數，它給了我們函數所需的時間。假設t(n)表示pow(x,n)所需的時間，即n的函數。

那麼我們可以得出結論，即t(0)=c，因爲如果我們調用pow(x,0)，我們要檢查是否（n==0），然後返回1，它可以在固定時間（因此不斷c）來完成。

現在我們考慮另一種情況：n>0。我們在這裏獲得t(n) = d + t(n-1)。這是因爲我們再次檢查n==1，計算，因此（t(n-1)），並將結果乘以x。檢查和乘法可以在恆定時間內完成（常數d），遞歸計算pow需要t(n-1)。

現在，我們可以在 「擴展」 一詞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 

那麼，如何長時間才能，直到我們達到t(1)？由於我們從t(n)開始，我們在每一步中減去1，因此需要n-1步驟才能達到t(n-(n-1)) = t(1)。另一方面，這意味着，我們得到n-1倍的常數d,t(1)評估爲c。

所以我們得到：

t(n) = 
... 
d + d + d + ... + c = 
(n-1) * d + c 

所以我們得到了t(n)=(n-1) * d + c這是O（n）的元素。

pow2可以使用Masters theorem來完成。因爲我們可以假設算法的時間函數是單調遞增的。所以現在我們有必要爲pow2(x,n)計算時間t(n)：

t(0) = c (since constant time needed for computation of pow(x,0)) 

爲n>0我們得到

 /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) 

上面可以 「簡化」 到：

t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing) 

所以我們獲得t(n) <= t(n/2) + d，這可以使用主人定理到t(n) = O(log n)來解決（參見應用於Popul ar維基百科鏈接中的算法，例如「二進制搜索」）。

Answer 2

它可能有點複雜，但我認爲通常的方法是使用Master's theorem。

Answer 3

兩種功能忽略遞歸複雜度爲O（1）

對於第一算法POW1（X，N）的複雜性爲O（n），因爲遞歸的深度，其中n呈線性相關。

對於第二個複雜度是O（log n）。這裏我們遞歸大約log2（n）次。拋出2我們得到日誌n。

Answer 4

所以我猜你正在提高x的權力n。 pow1需要O（n）。

你永遠不會改變x的值，但你每次從n取1，直到它變爲1（然後你就返回）這意味着你將遞歸n次。

Answer 5

讓我們從pow1開始，因爲這是最簡單的一個。

你有一個函數，在O（1）中完成一次運行。 （條件檢查，返回和乘法是不變的時間。）

你剩下的就是你的遞歸。你需要做的是分析函數最終會自動調用的頻率。在pow1中，它會發生N次。 N * O（1）= O（N）。

對於pow2，它是相同的原理 - 函數的一次運行在O（1）中運行。但是，這次你每次都將N減半。這意味着它將運行log2（N）次 - 有效地每比特一次。 LOG2（N）* O（1）= O（日誌（N））。

一些東西，可能會幫助你是利用一個事實，即遞歸總是可以表示爲迭代（並不總是很簡單，但它是可能的。我們可以表達POW1作爲

result = 1; 
while(n != 0) 
{ 
    result = result*n; 
    n = n - 1; 
} 

現在你有一個迭代算法相反，你可能會發現它更容易分析它的方式。

Answer 6

此鏈接爲您的問題提供確切的答案。這裏是源代碼（http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/recursion12.pdf）