2017-06-20 119 views
0
void f(int n) { 
    if (!n) return; 
    for (int i=0; i<8; i++) 
     f(n/12); 
    g(n,3); 
} 

void g(int n, int i) { 
    if (!i) return; 
    for (int j=n; j>0; --j) { 
     g(n,i-1); 
    } 
} 

我想估計這個功能。本複雜的複雜性是我做的方式:估計遞歸函數

  1. 估算摹複雜性。它取決於i的值,並且每個條目引發n個循環條目,因此整個複雜度爲Θ(n^3)。
  2. 現在開始f。 T(n)= 8 *(T/12)+ g(n,3)。現在應用主定理。 log(12)< 3(f的複雜度),所以f的整體複雜度爲Θ(n^3)。

這是正確的解決方案還是需要考慮其他方面?

+0

應該不是Θ(n^i)? – fafl

+0

是的。在這種情況下,我等於3,這就是爲什麼我寫它像n^3。 – amylis

+0

因此,如果每個f開始一個g和多個f,那麼f的複雜度是否應該不大於g? – fafl

回答

0

由於T(n)終止時n = 0T遞歸必須log12(T)深(忽略四捨五入和關閉的情況的一個等)

如果擴大系列,給你的結果爲g

enter image description here

括號中的第二項很小,因此可以忽略。因此總的複雜性是Θ(n^3)