計算大O字

-3

所以我要計算的大O此代碼片段，但我不確定如何處理它。一些幫助開始將不勝感激。計算大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++) 
       { 
        ... 
       }

來源

2013-04-10 Reyne

這看起來像功課。 – valverij 2013-04-10 16:09:10

下面是關於大O符號大規模的崗位：http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it – valverij 2013-04-10 16:12:32

第1內部循環爲O（n），外環Ø （sqrt（n）），這意味着O（n * log n）。第二個循環......我不得不說爲O（n），因爲當n趨於無窮大，內環轉到恆定的，但因爲我把數學這已經有一段時間，所以把它當作一粒鹽;） – 2013-04-10 16:20:41

好了，所以我們開始在第1內部循環，並認爲它是O(n)。然後，i從1變爲平方根n，因此該循環的複雜度爲O(sqrt(n))。然後我們將它們相乘以找出第一個嵌套循環的複雜度，即O(n * sqrt(n))。

第二個外環的複雜度爲n，內循環運行的定義次數（不依賴於n），因此總複雜度爲O(n * sqrt(n) + n)。

來源

2013-04-10 16:11:29 James

要注意的是，'O（n * sqrt（n）+ n）'與'O（n * log（n））'相同。 – 2013-04-10 16:55:06

大O是最壞的情況，在這種情況下是N^2，因爲你有一個嵌套的for循環的第一個for循環的內部。

第二組的for循環是僅由N大O，因爲內部的循環將最多的2000倍，在事物的運行範圍是非常小的，特別是當N是巨大的。

來源

2013-04-10 16:10:31 Justin

回答

相關問題