Big Oh（O）はアルゴリズムの平均ケースと最良ケースを表すのにも使われているのはなぜですか？

Question

ビッグああ、最悪の場合を表している場合、なぜそれが 平均がO(nlogn) あるクイックソートの時間計算などのアルゴリズム の平均と最高のケースを表すために使用されている最高のO(nlogn)の代わりOmega(nlogn)ある 最悪ですO(n^2)

Answer 1

ビッグ-Oはではないは最悪の場合（アルゴリズムの）です。むしろ、（漸近）上限を（関数上）に表します。アルゴリズムのベストケースまたは平均ケースのパフォーマンスの上限について議論することは、完全に有効であり、しばしば有用です。たとえそのうちの1つがより良い平均ケース性能を有するならば、どちらのアルゴリズムも同じ最悪ケース性能を有するとしても、実際には他のアルゴリズムよりも優れた性能を発揮し得る。

Answer 2

Big Oは、の複雑さは、特定の関数によって上限になることを示しています。

Big Oを使用して平均と最高のケースを説明しようとするとき、平均的なケースがその関数によって上限になっていると効果的に言います。

つまり、Big Oを使用して表現された平均ケースおよび最良ケース表現は、十分大きな値のnの場合、平均および最良の場合がその機能より悪くならないことを意味します。