两个for循环的时间复杂度

Question

所以我知道时间的复杂性:

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

是n ^ 2

但会:

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

是n + n？

Answer 1

由于big-O表示法不是要比较绝对复杂度,而只是比较相对的,O(n + n)实际上与O(n)相同.每次加倍x时,你的代码将花费两倍于之前的代码,这意味着O(n).你的代码是通过2个,4个还是20个循环无关紧要,因为无论100个元素需要多长时间,200个元素需要两倍的时间,10万个元素需要100倍的时间,无论多长时间这是在哪个循环中花费的.

这就是为什么big-O没有说绝对速度的原因.假设O(n ^ 2)函数f()总是比O(log n)函数g()慢,谁是错误的.big-O表示法只表示如果你继续增加n,那么g()将在速度上超过f(),但是,如果n在实践中总是保持低于该点,那么f()可以在实际程序代码中总是比g()快.

示例1
假设单个元素的f(x)为5 ms,单个元素的g(x)为100 ms,但f(x)为O(n ^ 2),g(x)为O(log2 n) ).时间图将如下所示:

注意:最多7个元素,f(x)更快,即使它是O(n ^ 2).
对于8个或更多元素,g(x)更快.

例2
二进制搜索是O(log n)的,理想的哈希表(无碰撞)为O(1),但请相信我,一个Hashtable并不总是总是比现实中的二进制搜索速度更快.使用良好的散列函数,散列字符串可能比整个二进制搜索花费更多的时间.在另一方面,使用较差的哈希函数创建大量的碰撞和碰撞越多意味着你的哈希表的查找会不会真的是O(1),因为大多数散列表解决冲突的方式,将查找或者是O(LOG2 N)或甚至O(n).

Answer 2

这将是2n,所以是的,你是对的.

它通常只表示为O(n),因为它是线性的而不是二次的.

它当然取决于循环中的代码,但我想你已经知道了.