计算大O字

Question

所以我要计算的大O此代码片段，但我不确定如何处理它。一些帮助开始将不胜感激。

`

  for (i = 1 ; i * i < n ; i++){ 
       for (j = 1 ; j < n ; j++) 
       { 
        ... 
       } 
      } 
      for (i = 1 ; i < n ; i++){ 
       for (j = i % 5 ; i + j < 2000; j++) 
       { 
        ... 
       } 

`

Answer 1

好了，所以我们开始在第1内部循环，并认为它是O(n)。然后，i从1变为平方根n，因此该循环的复杂度为O(sqrt(n))。然后我们将它们相乘以找出第一个嵌套循环的复杂度，即O(n * sqrt(n))。

第二个外环的复杂度为n，内循环运行的定义次数（不依赖于n），因此总复杂度为O(n * sqrt(n) + n)。

Answer 2

大O是最坏的情况，在这种情况下是N^2，因为你有一个嵌套的for循环的第一个for循环的内部。

第二组的for循环是仅由N大O，因为内部的循环将最多的2000倍，在事物的运行范围是非常小的，特别是当N是巨大的。