分析我的程序的时间复杂度
我在确定算法的时间复杂度时遇到问题。
for(int i=0;i <n i++){} O(n)
for(int i= 0 ;i<n ;i++){ O(n^2)
for(int j=0;j<n;j++){
}
}
现在，下面的代码的复杂度
for(i =0; i<n ; i++) {}
for (j=0;j<n ;j++ ) {}
是 O(2n)，因为它涉及 2 个单独的循环？
如果我开始 j =5 到 n 会怎样？
I have problem in determining time complexities of algorithms.
for(int i=0;i <n i++){} O(n)
for(int i= 0 ;i<n ;i++){ O(n^2)
for(int j=0;j<n;j++){
}
}
Now for following code whats the complexity
for(i =0; i<n ; i++) {}
for (j=0;j<n ;j++ ) {}
is it O(2n) as it invloves 2 seperate loops?
what if i start j =5 to n?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
没有
O(2n)，它只是O(n)。换句话说，它的扩展速度与n的增加相同。如果它是一个嵌套循环，则其时间复杂度为
O(n2)，但是{}的存在空块意味着它没有嵌套。无论你从 1 还是从 5 开始，它都没有区别，它仍然以
n为单位缩放，只是有一个稍微负的常数加法。因此仍然是O(n)。复杂度
O(n)、O(cn)和O(n+c)（其中c为常数）都是等价的。此外，您通常也只使用效果最高的术语。因此，您通常不会看到
O(7n3 + 3n2 + 12n + 2)，它将被简化为O (n3)。There is no
O(2n), it's justO(n). In other words, it scales at the same rate asnincreases.If it was a nested loop, it would be
O(n2)but the presence of your{}empty blocks means it isn't nested.And it makes no difference whether you start at one or five, it still scales with
n, just with a slightly negative constant addition. Hence stillO(n).The complexities
O(n),O(cn)andO(n+c)(wherecis a constant) are all equivalent. In addition, you also generally only use the term with the highest effect.So you won't usually see
O(7n3 + 3n2 + 12n + 2), that will be simplified toO(n3).不存在 O(2n) 这样的东西。时间复杂度是指算法如何扩展到无穷大，而不是其实际运行时间。在您的示例中，您有两个循环，它们都是线性 [ O(n) ] 时间的，这意味着它们将随着输入线性缩放，因此您的整体算法是 O(n) 。
如果开始 j=5，它仍然是 O(n)，因为它仍然线性缩放。
所以本质上，O(2n) == O(n)。
There is no such thing as O(2n). Time complexity refers to how an algorithm scales to infinity, not to its actual running time. In your examples, you have two loops that are both linear [ O(n) ] time, meaning that they will scale linearly with the input, hence your overall algorithm is O(n).
If you start j=5, it's still O(n) because it still scales linearly.
So in essence, O(2n) == O(n).
时间复杂度有两个重要规则，当且仅当 n 的值非常大时才适用...
高阶项的系数可以忽略。
可以忽略所有低阶项。
为什么这些假设非常简单，让我们考虑一个例子： -
假设时间复杂度为 5n^2 + 3n 。当 n 值非常低时，系数和低阶项会因 n 的微小变化而变得突出。但假设如果n的值很大，低阶项对时间复杂度的影响就很小，而且最高阶项的系数也可以用同样的方式忽略。
请注意，仅当 n 理论上接近无穷大时，时间复杂度才发挥重要作用。
There are two important rules of Time complexity which applies if and only if the value of n is very large...
The coeffeicient of the higher order term can be neglected.
All lower order terms can be igonred.
Why these assumptions are quite simple, let`s consider an example:-
Suppose the time complexity is 5n^2 + 3n . At very low values of n, the coefficient and the lower order terms gets prominent for a small change in n. But suppose if the value of n is very large, the effect of the lower order term on the time complexity is very less and moreover the coefficient of the highest order term can also be ignored in the same way.
Note time complexity plays a major role only when n approaches infinity theoritically.
最终结果是，通过一些我不记得的奇特数学，你可以将 2n 这样的东西变成大 O(n)。这些系数被视为常数，因为我们关心复杂性，并且在单独处理该问题时，您需要检查方程中导致最大增长的部分。在这种情况下，Big O(n^2) 是方程复杂性中最主要的元素。因此，您的算法被认为是 Big O(n)。
我很抱歉，由于误读了最后几行代码而导致了小拼写错误。你问的那个是 Big O(n)
The end result is that through some fancy math that I cannot remember, you are able to turn things like 2n into just big O(n). The coefficients are considered constants because we are concerned with the complexity and when dealing with that issue alone, you need to examine the part of an equation that causes the most growth. In this case, Big O(n^2) is the most predominate element within the complexity of the equation. Therefore, your algorithm is considered to be Big O(n).
my apologies, small typo based on misreading the last lines of code. The one you asked about would be Big O(n)
是的，它是 O(2n)，但这与 O(n) 相同，因为在渐近复杂度中乘以常数并不重要。类似地，如果跳过前五个元素，则循环需要 O(n-5) 时间，但这也与 O(n) 相同，因为添加或减去一个常数甚至比乘以一个常数还要弱。有关定义，请参见例如 http://en.wikipedia.org/wiki/Big_O_notation。
Yes, it's O(2n), but that is the same as O(n), because multiplying by a constant does not matter in asymptotic complexity. Similarly, if you skip the five first elements, your loop takes O(n-5) time, but that too is the same as O(n), because adding or subtracting a constant is even weaker than multiplying by a constant. See e.g. http://en.wikipedia.org/wiki/Big_O_notation for the definitions.
复杂性是对描述关系输入 n 和时间的函数形状的度量。
请记住，没有常数，因为在大多数情况下您不知道常数。如果您比较两个可比较的算法，您可能会使用常量，但在大多数情况下，您会引用通用复杂性并使用某些输入 n 来测量时间。在你的情况下， O(2*n) 与 2*O(n) 相同，这只是 O(n) 因为 2*O(n) 并没有说明太多，并且可以仅使用常数 2 与之前的进行比较算法。说第二个算法的复杂度为 2*O(n) 并没有多大意义。
以这种方式看待复杂性。
假设您有一个需要 n = 100 万的算法。
大概的大小或操作次数的顺序是多少
Complexity is measurement for shape of function that describes relation input n and time .
Keep in mind that there is no constant becuase in most cases you do not know constant. You might use constant if you compare two comparable algorhitms, but in most cases you would cite generic complexity and measure time whit some input n. In your case case O(2*n) is same as 2*O(n) and this is just O(n) since 2*O(n) does not say much as is and can be compared using constant 2 only whit previous algorithm. Saying that second algorithm has complexity 2*O(n) does not have not much sense.
Look on complexity in this way.
Lets say that you have algorithm that takes n = one million.
What is approximate size or order of number of operations