void foo (int n, int val)
{
int b,c; //+1
for (int j = 4; j < n; j++) //n
{
for (int i = 0; i < j; i++) //n
{
b = b * val; // +1
for (int k = 0; k < n; ++k) // n
c = b + c;
}
}
}
我有上面的代码,当我尝试解决它时,我得到了 T(n) 的各种答案。从我的各种答案(n3-7n2+2)/2 和 ((n3 -5n2 +6n)/2)+ 2n - 6,我得出的结论是 O(n) 是 O(n3)。我只需要找到正确的 T(n)。
最佳答案
现在是凌晨 4 点,所以我可能在胡说八道,但我的想法是:
第一个for是n-3次迭代
第二个 for 是 4+5+6+7+...+n-1 次迭代 => 1/2(n² - n - 12)
第三个for是n次迭代
(n-3)*(1/2(n² - n - 12))*n => O(n^4)
关于algorithm - 嵌套 for 循环的 T(n) 时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33269648/