如何計算Big-O？

-10

public long seriesLoop() { 
    long answer = a;   
    for (long i = 1; i < n; i++) {   
     long delta = a;    
     for (long j = 0; j < i; j++) { 
      delta *= r;    
     }   
     answer += delta;   
    }  
    return answer; 
} 

public long seriesClosedForm() { 
    return (long) (a * (1 - Math.pow(r, n))/(1 - r));  
}

這兩種方法的Big-O符號是什麼？爲什麼？我們如何計算算法的大O？如何計算Big-O？

來源

2017-07-30 J.Pei

我投票結束這個問題作爲題外話，因爲這是家庭作業轉儲。 – Guy

你根據循環計算大O.一個循環= O（n）。嵌套循環= O（n^2） –

@ j.pei請仔細閱讀此stackoverflow [線程]（https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it）。這會給你清晰的想法。大O. –

對於第一種方法，它是n * n = n^2。由於有兩個循環，每個循環 O（n）是n，因爲您正在瀏覽數組中的每個項目。

第二個是一個常數o（1）。

來源

2017-07-30 10:47:13

是的，這是我的答案。但我的導師說，第一個應該是O（n），第二個不是O（1），它是O（log n）。我不知道爲什麼.. –

如何計算Big-O？

回答

相關問題