我对如何确定此语句中 while 循环的时间复杂度感到困惑:
procedure P (integer n);
for (i: 1 to n)
x := n;
while (x > 0)
x := x - i;
我知道 for 循环运行 (n-1) 次。起初我以为 while 循环会运行 n 次，因为我把 i 误认为是 1，但事实并非如此。我一直在输入数字以查看程序何时停止，但没有看到一致的模式。我注意到随着 n 的增加，while 循环运行的时间更长(但不是很多)所以这可能是对数的吗？提前致谢。
最佳答案
第一次运行进行 n 个 while 循环
第二次运行使 n/2 个 while-cycles
第三次运行 n/3 个 while-cycles
第 k 次运行使 n/k while 循环
所以总时间正比于
n * (1/1 + 1/2 + 1/3 +...+1/n)
在括号中我们可以看到 harmonic series 的部分和, 趋于n的自然对数，复杂度为O(n log n)
关于algorithm - 嵌套while循环的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40101669/