两个for循环的时间复杂度 [英] Time Complexity of two for loops

问题描述

所以，我知道的时间复杂度：

So I know that the time complexity of:

for(i;i<x;i++){
   for(y;y<x;y++){
      //code
   }
}

为n ^ 2

is n^2

但将：

for(i;i<x;i++){
   //code
}
for(y;y<x;y++){
   //code
}

是N + N？

be n+n?

推荐答案

由于大O表示法是不是比较绝对的复杂性，但只是相对的，O（N + N），其实是同为O（n ）。每次你双重X，你的code将采取两次只要它之前，这意味着为O（n）。您的code无论是通过2个，4个或20圈没有关系，因为无论花费的时间为100个元素运行时，它会花时间的两倍为200元和100倍的时间，10000元，无论怎么那么多时间，这循环中度过的。

Since the big-O notation is not about comparing absolute complexity, but only relative one, O(n+n) is in fact the same as O(n). Each time you double x, your code will take twice as long as it did before and that means O(n). Whether your code runs through 2, 4 or 20 loops doesn't matter, since whatever time it takes for 100 elements, it will take twice the time for 200 elements and 100 times the time for 10'000 elements, no matter how much time of that is spent within which loop.

这就是为什么大O是不是说关于绝对速度东西。谁假设一个为O（n ^ 2）函数f（）总是比O（log n）的函数g（）更慢，是错误的。大O符号只能说，如果你不断增加N，会有一个点，G（）是要超越F（）的速度，但是，如果n始终保持低于在实践中该点，则f（）即可总是比克（）在实际的程序code更快。

That's why big-O is not saying anything about absolute speed. Whoever assumes that a O(n^2) function f() is always slower than a O(log n) function g(), is wrong. The big-O notation only says that if you keep increasing n, there will be a point where g() is going to overtake f() in speed, however, if n always stays below that point in practice, then f() can always be faster than g() in real program code.

例1
假设函数f（x）需要5毫秒为一个单一元件以及g（x）的需要100毫秒为单个元件，但函数f（x）为O（n ^ 2），克（x）是O（LOG2 n）的。时间图如下所示：

Example 1
Let's assume f(x) takes 5 ms for a single element and g(x) takes 100 ms for a single element, but f(x) is O(n^2), g(x) is O(log2 n). The time graph will look like this:

注：截至7元，F（x）是更快，即使它是O（n ^ 2）
。 为8或以上的元素，克（x）是更快。

Note: Up to 7 elements, f(x) is faster, even though it is O(n^2).
For 8 or more elements, g(x) is faster.

例2
二进制搜索是O（log n）的，理想的哈希表​​（无碰撞）为O（1），但请相信我，一个哈希表是迄今为止总是比现实中的二进制搜索速度更快。使用一个好的哈希函数，散列字符串可能需要更多的时间比整个二进制搜索一样。在另一方面，用可怜的哈希函数产生大量的碰撞和更多的碰撞意味着你的哈希表的查找不会真正为O（1），因为大多数哈希表解决冲突的方式，将查找或者是O（LOG2 N）或即使是为O（n）。

Example 2
A binary search is O(log n), an ideal hashtable (without collisions) is O(1), but trust me, a hashtable is by far always faster than a binary search in reality. Using a good hash function, hashing a string can take more time than the whole binary search does. On the other hand, using a poor hash function creates plenty collisions and the more collisions means that your hashtable lookup will not really be O(1), because most hashtables solve collisions in a way that will make lookups either O(log2 n) or even O(n).

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