估计递归函数
问题描述：
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）。
这是正确的解决方案还是需要考虑其他方面？
答
由于T(n)终止时n = 0的T递归必须log12(T)深（忽略四舍五入和关闭的情况的一个等）
如果扩大系列，给你的结果为g：
括号中的第二项很小，因此可以忽略。因此总的复杂性是Θ(n^3)。
应该不是Θ（n^i）？ – fafl
是的。在这种情况下，我等于3，这就是为什么我写它像n^3。 – amylis
因此，如果每个f开始一个g和多个f，那么f的复杂度是否应该不大于g？ – fafl