这些循环1和2的时间复杂度是多少

Question

我在一个非常受欢迎的网站上看了一篇关于循环时间复杂度分析的文章（链接如下），根据这篇文章，第一和第二个循环的时间复杂度分别是O（1）和O（n）。但是我认为两个循环的时间复杂度是相同的O（n）

for (int i = 1; i <= c; i++) {  
    // some O(1) expressions
}

我的推理是：`c*n=O（n）

看完下面的答案后，我的推理是错误的，因为没有变化的输入n。循环运行是固定的-c次。因此，无论输入值n是多少，循环都将以恒定时间运行。so（1）复杂性

for (int i = 1; i <= n; i += c) {  
    // some O(1) expressions
}

我的推理：c*n=O（n）

我错过什么了吗？如果有人能帮忙解释，我将不胜感激

这是文章的链接：http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

Answer 1

1）图中没有n，我不知道你为什么认为它是O（n）。循环从1到c，所以它的O（c），因为c是常数，所以复杂度是O（1）。

2） 循环从1开始，一直到n，每一步都递增c。很明显，复杂度是O（n/c），渐近地是O（n）。

Answer 2

对于（int i=1；i

这里c是一个常数。因此，基本上，无论n的值是多少，您都在执行常量操作。这就是为什么它被认为是恒定的复杂性，O（1）。

对于（int i=1；i

您使用的是一个输入值n，该值基本上随程序或算法的给定输入而变化。现在，c又是一个常数，对于n的所有不同值，它都将保持不变。复杂性被认为是O（n）。

对于（int i=1；i

这仅与上面相同，只是c的值是1。

所有的复杂性都以渐近表示格式表示。常数因子被删除，因为无论n的值如何，它们都是相同的。

Answer 3

循环或递归的运行次数为常量也被认为是O（1）。

这里：C是一个常量。因此，基本上，无论n

   // Here c is a constant   
   for (int i = 1; i <= c; i++) {  
        // some O(1) expressions
   }

也在第二循环中：

for (int i = 1; i <= n; i += c) {  
    // some O(1) expressions
}

你的理由不正确。这里的增量为C。对于n元素，循环出现n/c这是渐进的O（n/c）~O（n）