嵌套while循环的时间复杂度

Question

我对如何在此语句中确定 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 循环运行的时间更长（但不是很多）所以这可能是对数的吗？提前致谢。

Answer 1

第一次运行 n 个 while-cycles
第二个运行 n/2 个 while-cycles
第三个运行 n/3 个 while-cycles 第
k 个运行 n/k 个 while 周期

所以总时间与

n * (1/1 + 1/2 + 1/3 +...+1/n)

在括号中我们可以看到谐波级数的部分和，趋于n的自然对数，复杂度为O(n log n)