我是否过度简化了计算复杂性

Question

我只是想计算一些程序片段的复杂性，但是我担心我做的事情太简单了。如果我把我的碎片和答案放下来，你能告诉我我是否做错了吗？

（一个）

sum = 0;
for (i = 0;i < n;i++)
    sum++;

答案：n，只有一个for循环

（b）中

sum = 0;
for (i = 0;i < n;i++)
    for (k = 0;k < n*n;k++)
        sum++;

答案：n ^ 2因为嵌套循环，虽然我想知道嵌套循环中的n * n是否使它成为n ^ 3

（C）

sum = 0;
for (i = 0;i < n;i++)
    for (k = 0;k < i;k++)
        sum++;

答案：n ^ 2

（d）

sum = 0;
for (i = 0;i < n;i++)
    for (k = 0;k < i*i;k++)
        sum++;

答案：n ^ 2，但我和b有同样的担忧

（E）

sum= 0;
for (i = 0;i < n;i++)
    for (k = i;k < n;k++)
        sum++;

答案：n ^ 2

Answer 1

由于在所有示例中主要操作都是sum++，因此我们必须计算执行此基本操作的次数。

此外，在所有情况下，还有i++操作，也是重要的，以及k++。最后，这些计数器必须在每一步都与它们的限制进行比较，我们也应该将这些比较考虑在内。现在，这些额外的操作不会改变迭代次数;他们只是让每次迭代更加昂贵。例如，

（一个）

sum = 0;
for (i = 0;i < n;i++)
  sum++;

重复n次：i++，sum++和i<n，所有这些都给出了类似复杂性的3n操作。这就是为什么总的复杂性是O(n)。

一旦理解了这一点，就不再需要详细分析复杂性，因为big-O表示法将处理这些额外的计算。

第二个例子

sum = 0;
for (i = 0;i < n;i++)
  for (k = 0;k < n*n;k++)
    sum++;

重复n时间的操作

  for (k = 0;k < n*n;k++)
    sum++;

由于前面的情况，这个操作具有复杂性O(n*n)，因为这里的限制是n*n而不是n。因此总的复杂性是O(n*n*n)。

第三个例子是类似的，只是这次执行n次的操作是

for (k = 0;k < i;k++)
    sum++;

其复杂性随i而变化。因此，不是乘以n而是我们必须总结n不同的东西：

O(1) + O(2) + ... + O(n)

由于O中隐含的常数因子总是相同的（=在每个基本步骤中增加或比较的变量数），我们可以将其重写为

O(1 + 2 + ... + n) = O(n(n+1)/2) = O(n*n)

其他示例类似，因为可以按照这些相同的想法对它们进行分析。