估计递归函数

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）。

这是正确的解决方案还是需要考虑其他方面？

来源

2017-06-20 amylis

应该不是Θ（n^i）？ – fafl

是的。在这种情况下，我等于3，这就是为什么我写它像n^3。 – amylis

因此，如果每个f开始一个g和多个f，那么f的复杂度是否应该不大于g？ – fafl

由于T(n)终止时n = 0的T递归必须log12(T)深（忽略四舍五入和关闭的情况的一个等）

如果扩大系列，给你的结果为g：

括号中的第二项很小，因此可以忽略。因此总的复杂性是Θ(n^3)。

来源

2017-06-23 10:58:16 spug

估计递归函数

回答

相关问题