大哦表示法

Question

只需要確認一件真正快速的東西。 如果一個算法需要n(n-1)/2測試運行，那麼大哦O(n^2)？

Answer 1

N（N-1）/ 2膨脹到(n^2 -n)/2明顯更小的所有n>=1，即(n^2/2) - (n/2)

(n^2/2)和(n/2)是這兩個功能組件，其中n^2/2占主導地位。 因此，我們可以忽略- (n/2)部分。

從n^2/2您可以安全地刪除/ 2部分漸近符號分析。

這簡化了 n^2

所以，是的，它是在爲O（n^2）

Answer 2

是的，這是正確的。

n(n-1)/2擴展到n^2/2 - n/2：

線性項n/2脫落，因爲它是低階的。這留下了n^2/2。常數被吸收到大O中，留下n^2。

Answer 3

是：

n(n-1)/2 = (n2-n)/2 = O(n^2) 

Answer 4

是的，它是。 n(n-1)/2是(n^2 - n)/2，這比c*n^2如果你選擇一個c這是至少爲1