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

Question

我在一个非常受欢迎的网站上阅读了一篇关于循环时间复杂度分析的文章（下面给出了link），根据那篇文章，下面第一个和第二个循环的时间复杂度是 O(1 ) 和 O(n) 分别。但我认为两个循环的时间复杂度是相同的 O(n)

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

我的推理：`c*n=O(n)

after going through answers below , My reasoning is wrong as there is no varying input n. the loop run is fixed- c times. hence irrespective of the input value n , the loop will run constant time. so O(1) complexity

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

我的推理：c*n=O(n)

我是不是遗漏了什么？如果有人能帮忙解释一下，我将不胜感激

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

Answer 1

1)图中没有n，不知道你为什么会这么想O(n)。 loop 是从 1 to c 开始的，所以它是 O(c)，并且由于 c 是一个常数，所以复杂度是 O(1)。

2) 循环从1开始，直到n，每一步递增c。显然，复杂度为 O(n/c)，渐近为 O(n).

Answer 2

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

这里c是一个常量。所以基本上，无论 n 的值如何，您都在执行恒定数量的操作。这就是为什么它被认为是恒定的复杂性，O(1).

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

您正在使用输入值 n 进行循环，该输入值基本上随程序或算法的给定输入而变化。现在 c 又是一个常量，对于 n 的所有不同值都将保持不变。复杂度被认为是 O(n).

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

这只是和上面一样，只是c的值是1。

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

Answer 3

A loop or recursion that runs a constant number of times is also considered as 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 = O(n) 不正确。这里增加 C。对于 n 个元素，循环发生 n/c 渐近 O(n/c) ~ O(n)

Answer 4

O(1) : 这个循环的复杂度是 O(1) 因为它运行的时间是常数 c.

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

O(n): 循环的复杂度是O(n)如果它递增或递减一个常数。例如，这些循环具有 O(n) 时间复杂度。

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

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

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

What is the time complexity of these loops 1 and 2

algorithm

time-complexity