if（N^2％N == 0）的大O符號的時間

我想了解如何計算if語句的時間複雜度。我得到了這個問題：if（N^2％N == 0）的大O符號的時間

sum = 0; 

for(i=0;i<n;i++) 
{ 
    for(j=1;j<i*i;j++) 
    { 
     if(j%i==0) 
     { 
      for(k=0;k<j;k++) 
      { 
       sum++; 
      } 
     } 
    } 
}

現在，我明白，線（1）和（2）我有n個^ 3個，並且根據我的教授的總時間爲n^4，我也看到if語句正在測試以檢查n^2/n的其餘部分是否爲0，並且我認爲第（4）行中的for循環應該是n^2，但是我不知道如何計算它（3）至（4）的順序總共具有O（n）。歡迎任何幫助。提前致謝。

來源

2015-10-20 Jorge Vargas Moreno

我看不出總的時間怎麼可能是'O（n^4）' - 它看起來像'O（n^3）'給我。 –

@DavidSchwartz這是因爲第二個循環運行到'我*我'，這是'n^2'次。 – user58697

@ user58697但是它每次增加'i'（當'j'不是'i'的倍數時，什麼都不會發生）。 –

這裏有6行實際的代碼。（你讓他們都在同一行這是非常難以閱讀。約翰·奧多姆固定的。）

1）運行在O（1）

2）運行在O（n）的總數爲O（ N）

3）運行在O（N^2），總爲O（n^3）

4）運行在O（1），該過濾傳入從爲O（n^3）至O（n^2）

編輯：我錯過了這個循環去n^2而不是n的事實。

5）爲O（n運行），但此n是原始n的平方，因而它是真正爲O（n^2），總是O（n^4）

6）運行O（ 1）中，總是O（n^4）

因此，總時間爲O（n^4）

注意，但是：

for(j=1;j<i*i;j++) 
    { 
     if(j%i==0)

這就要好得多改寫爲

for(j=i;j<i*i;j+=i)

（希望我的語法正確，它一直年齡，因爲我已經做C.）

來源

2015-10-20 22:47:15

應該不是5）是O（n^2），因爲k要去的j將要去我^ 2哪裏我要去n因此使k從0到n^2？ –

@JorgeVargasMoreno Argh，你是對的 - 我專注於過濾器，並錯過了第二個循環進入n^2的事實。 –

好的，現在過濾器是如何工作的，爲什麼它總是從O（n^3）到O（n^2）？這是否會發生每一個如果還是因爲％被檢查在if？ –

讓我們通過重寫程序，並觀察一些數學公式計算sum：1

階段：

for (i = 0; i < n; i++) { 
     for (j = 0; j < i*i; j += i) { 
      sum += j; 
     } 
    }

階段2（利用算術級數）：

for (i = 0; i < n; i++) { 
     sum += i*i * (i + 1)/2; 
    }

第3階段：

Sum of cubes is a polynomial 4th degree

所以，sum = O(n^4)。原來的程序通過加1來實現，因此需要增加O(n^4)。

來源

2015-10-20 22:56:51 user58697

if（N^2％N == 0）的大O符號的時間

回答

相關問題