1) i=s=1;
while(s<=n)
{
i++;
s=s+i;
}
2) for(int i=1;i<=n;i++)
for(int j=1;j<=n;j+=i)
cout<<"*";
3) j=1;
for(int i=1;i<=n;i++)
for(j=j*i;j<=n;j=j+i)
cout<<"*";
有人可以解释一下这三个代码的时间复杂度吗？
我知道答案，但我不明白它是怎么来的
1)要弄清楚这一点，我们需要弄清楚循环x次迭代中的s有多大。然后，我们将知道在达到条件s > n之前发生了多少次迭代。
在第x次迭代中，变量i具有值x + 1变量s的值等于所有先前值的i之和。因此，在该迭代中，s的值等于
sum_{y = 1 .. x} (y+1) = O(x^2)
这意味着我们已经s = nx = O(sqrt{n})迭代。这就是循环的运行时间。
如果你不确定为什么总和是O(x^2)的，我在这里回答了另一个这样的问题，同样的技术适用。在这种特殊情况下，您还可以使用标识
sum_{y = 1 .. x} y = y choose 2 = (y+1)(y) / 2
这个恒等式可以很容易地通过y的归纳来证明。
2)尝试分析内循环运行多长时间，作为i和n的函数。因为我们从 1 开始，以n结束，然后按i计数，它运行了n/i次。所以外循环的总时间为
sum_{i = 1 .. n} n/i = n * sum_{i = 1 .. n} 1 / i = O(n log n)
sum_{i = 1 .. n} 1 / i级数称为谐波级数。众所周知，它收敛到O(log n).我不能在这里附上一个简单的证明。不过，可以用微积分来证明。这是一个你必须知道的系列。如果你想看到一个简单的证明，你可以在维基百科的"比较测试"中查看。那里的证明只显示序列是>= log n，但同样的技术也可以用来证明它也<= O(log n)。
3.)这看起来像是一个棘手的问题。内部循环将运行一次，但是一旦它以j = n + 1退出，我们永远无法重新进入这个循环，因为以后运行的行不会再次j <= n。我们将多次运行j = j * i，其中i是正数。所以j最终至少会和n!一样大.对于任何重要的n值，这将导致溢出。忽略这种可能性，代码总共将执行O(n)操作。