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);
}
}
我想估計這個功能。本複雜的複雜性是我做的方式:估計遞歸函數
- 估算摹複雜性。它取決於i的值,並且每個條目引發n個循環條目,因此整個複雜度爲Θ(n^3)。
- 現在開始f。 T(n)= 8 *(T/12)+ g(n,3)。現在應用主定理。 log(12)< 3(f的複雜度),所以f的整體複雜度爲Θ(n^3)。
這是正確的解決方案還是需要考慮其他方面?
應該不是Θ(n^i)? – fafl
是的。在這種情況下,我等於3,這就是爲什麼我寫它像n^3。 – amylis
因此,如果每個f開始一個g和多個f,那麼f的複雜度是否應該不大於g? – fafl