嵌套while循环的时间复杂度

Question

我对如何确定此语句中 while 循环的时间复杂度感到困惑：

procedure P (integer n);
 for (i: 1 to n)
   x := n;
   while (x > 0)
         x := x - i;

我知道for循环了运行s (n-1) 次。起初我以为 while 循环会运行 n 次，因为我把 i 误认为是 1，但事实并非如此。我一直在输入数字以查看程序何时停止，但没有看到一致的模式。我注意到随着 n 的增加，while 循环运行s 变长了（但不多）所以这会不会是对数的？提前致谢。

Answer 1

第一个运行产生 n 个 while 循环
第二个运行使得 n/2 while-cycles
第三个运行使得 n/3 while-cycles
第 k 个运行使 n/k 而循环

所以总时间正比于

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

括号中可以看到harmonic series的部分和，趋于n的自然对数，复杂度为O(n log n)

Answer 2

MBo回答的很详细。如果到目前为止，您可能会问自己，为什么第一个运行有 n 个 while 循环，第二个运行 n/2 个 while 循环，等等

     x := n;
     while (x > 0)
         x := x - i;

所有循环运行直到x==0由while循环

的条件

因此第一个 while 循环运行：n-t*1=0 次整数 t 和 i==1

第二个 while 循环运行：n-t*2=0 次整数 t 和 i==1

所以我们得到第一个n=t第二个n=2t所以n/2=t第三个n/3=t

Time complexity of nested while loop