int function2(int n)
{
int i, j, k;
int sum = 0;
for (k = 1; k <= n; k += 1)
{
for (i = 1; i <= n; i *= 3)
{
j = i;
while (j > 1)
{
sum += 1;
j /= 3;
}
}
}
return sum;
}本人理解：
最外层的for循环运行了n次，最内层的for循环运行了log3（n）次，最内层的while循环运行了log3（i）次，由于i以log3（n）的速率增加，while循环运行了log3（log3（n））次，所以总的复杂度是O（n * logn * log（logn））。
但是想一想，while循环运行的次数不应该和i乘以3的次数相同吗？所以我们能不能把它重写为：
for (k = 1; k <= n; k++)
for (i = 1; i <= log3(n); i++)
for (j = 0; j < i; j++)时间复杂度O（n * logn * logn）
也有人说它是O（n * logn），因为它是调和级数，这怎么是调和级数？
1条答案
按热度按时间qhhrdooz1#
那么总的复杂度是O（n * logn * log（logn））？
没有。
while循环运行的次数是否与i乘以3的次数相同
是的。
在这种情况下它就是O（n * logn * logn）
是的。
对于中间循环的给定迭代，最内部的循环将循环log3次，但是是3的幂，所以实际上对于中间循环的每个下一次迭代，内部循环将比之前多做一次迭代。𝑖 times for a given iteration of the middle loop, but 𝑖 is a power of 3, so actually with each next iteration of the middle loop, the inner loop will doonemore iteration than before.
中间循环的组合迭代的内部循环迭代次数-对于一个外部迭代-为以下总和：
1 + 2 + 3 +...+对数3𝑛
这是一个triangular number，所以这是O（log ²）。𝑛).
将外环代入方程，得到：O（对数平方）𝑛log²𝑛)