ビッグオービル

Question

本当に素早く何かを確認する必要があります。 アルゴリズムがn(n-1)/2のテストを実行する場合は、大きなoh O(n^2)ですか？

Answer 1

のn（n-1）のだcを選ぶ場合は、すべてのn>=1のために明確にc*n^2よりも小さい、(n^2 - n)/2です/ 2それは(n^2/2) - (n/2)

(n^2/2)と(n/2)で、(n^2 -n)/2にされている拡張し2つの機能コンポーネントのうち、n^2/2が支配的です。 したがって、- (n/2)部分は無視できます。

n^2/2から、漸近表記解析で/ 2部分を安全に削除できます。

これは、したがって、はい、それはOである（N^2） n^2

に簡素化

Answer 2

はい、正しいです。

n(n-1)/2はn^2/2 - n/2に展開：

それは下位のだから落ちるn/2線形用語。これはn^2/2となります。定数はbig-Oに吸収され、n^2のままです。

Answer 3

はい：

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

Answer 4

はい、そうです。 n(n-1)/2あなたは、少なくとも1