algorithm - マージソート実行時間 BigO

Question

Snape の「魔法使いにとって不親切なアルゴリズム」の教科書では、マージ ソートの実行時間は O(n^4) であると主張しています。この主張は正しいですか？

解決策: はい。O(n^4) はアルゴリズムにかかる時間の上限しか与えないため、この主張は技術的に正しいです。ただし、タイトな境界はΘ(n log n).

解決策が何を述べているのかよくわかりません。O(n^4) はどのように正しいのでしょうか?

Answer 1

Big O 表記は、アルゴリズム ランタイムの最悪のケースの上限です。

O(n^4) はマージソートの最悪のケースの時間を超えているため、境界を提供するため、技術的には正しいです。Mergesort のパフォーマンスが O(n^4) より悪くなることはありません。

ただし、実行時間のより適切な表現は O(n log n) であるため、これは役に立ちません。これは、マージソートの「最も厳しい」境界です。

Answer 2

Big-O は、(foo) 以上の速度で実行されるすべてを含むセットです。Little-O は、(foo) よりも厳密に高速に実行されるもののセットです。マージソートが O(n^4) であると言うのは正しいですが、それは Theta(n log n) であるため、あまり役に立ちません。マージソートが o(n^4) であると言う方がわずかに便利です。

さらに複雑なことに、ほとんどのキーボードにはシータがないという理由だけで、ビッグシータの方が適切な場合にビッグオーが使用されることがよくあります。