三个代码的时间复杂度，其中变量彼此依赖

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<<"*";

有人能解释我这三个代码的时间复杂度吗？
我知道答案，但我不明白它是怎么来三个代码的时间复杂度，其中变量彼此依赖

来源

2017-09-08 WRICK

请尽可能多地描述您对时间行为以及从中获取时间复杂度的理解。对所有方面的完整解释过于宽泛。您可能还想阅读[旅游]，尤其是[问]。我可以想象为什么你不想显示已知的答案，但如果你这样做，它可能更适合回答问题。 – Yunnosch

1）为了搞清这一点，我们需要弄清楚s多大的x“次循环迭代。然后我们会知道有多少迭代发生，直到达到条件s > n。

在x“次迭代中，变量i具有值x + 1 和可变s具有值等于i所有先前值的总和。因此，在该次迭代，s的值等于

sum_{y = 1 .. x} (y+1) = O(x^2)

这意味着，我们必须s = n对x = O(\sqrt{n})迭代。这就是循环的运行时间。

如果你不清楚为什么总数是O(x^2)，我给出了这样的另一个问题的答案一次here和相同的技术适用。在这种特殊情况下，你也可以使用一个身份

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)操作。

来源

2017-09-08 06:22:29

三个代码的时间复杂度，其中变量彼此依赖

回答

相关问题