这些循环1和2的时间复杂度是多少 [英] What is the time complexity of these loops 1 and 2

问题描述

我在一个非常受欢迎的网站上浏览了一篇关于循环时间复杂度分析的文章(下面给出了链接)，并且根据该文章，循环1st和2nd之下的时间复杂度分别为O(1)和O(n)分别.但是我认为两个循环的时间复杂度是相同的O(n)

I was going through an article on analysis of time complexity of loops at a very popular website(link given below) and according to that article the time complexity of below loops 1st and 2nd are O(1) and O(n) respectively. But i think the time complexity of both loop is same O(n)

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

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

My reasoning : `c*n=O(n)

经过下面的回答后，我的推理是错误的，因为没有变化的输入n.循环运行是固定的-c次.因此，不管输入值n为何，循环都将运行恒定时间.所以O(1)复杂度

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)

我错过了什么吗?如果有人可以提供帮助和解释，我将不胜感激

Am i missing something ?I would be grateful if someone can help and explain

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

推荐答案

运行一定次数的循环或递归也是视为O(1).

A loop or recursion that runs a constant number of times is also considered as O(1).

在这里: C 是一个常数.因此，基本上，无论 n

Here: C is a constant value. So basically, you are performing constant number of operation irrespective of the value of 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)

Your reason c*n = O(n) is not correct. Here Increment by C. For n elements, loops occur n/c which is asymptotically O(n/c) ~ O(n)

这篇关于这些循环1和2的时间复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！