n log n > n-- しかし、これはpseudo-linear関係のようなものです。 の場合n=1 billion、log n ~ 30;
したがって、 は の順序にn log nなります。 間のこの時間計算量の違いが現実世界で重要であるかどうかが気になります。30 billion30 X nnn log n and n
例:quick selectソートされていない配列内の k 番目の要素を検索するには、O(n)クイック選択アルゴリズムを使用します。
配列をソートして k 番目の要素を探すと、 になりますO(n log n)。要素を含む配列をソートするには、と を実行すると遅く1 trillionなります。60 timesquicksortindex it
ベストアンサー1
Big-O 表記法の主な目的は、投稿で行ったような推定を行い、一般的に高度なアルゴリズムをコーディングする労力が、コードの改善で発生する追加の CPU サイクルに見合うかどうかを自分で判断できるようにすることです。状況によっては、データセットが比較的小さい場合でも、異なる答えが得られる場合があります。
- モバイルデバイスで実行していて、アルゴリズムが実行時間の大部分を占める場合、CPUの使用を減らすとバッテリー寿命が延びます。
- 高頻度取引システムのような、全か無かの競争環境で運営している場合、マイクロ最適化によって利益と損失を区別できる可能性があります。
- プロファイリングにより、問題のアルゴリズムがサーバー環境での実行時間の大部分を占めていることがわかった場合、より高速なアルゴリズムに切り替えると、すべてのクライアントのパフォーマンスが向上する可能性があります。
Big-O 表記法で隠されているもう 1 つのことは、定数の乗算係数です。たとえば、Quick Select には非常に合理的な乗数があるため、非常に大きなデータ セットでこれを使用することで時間を節約できるため、実装する手間をかける価値は十分にあります。
もう一つの留意点は、空間計算量です。多くの場合、O(N*Log N)時間計算量のあるアルゴリズムには空間計算量がありますO(Log N)。これは、たとえばスタック容量が制限されたシステムで再帰関数を実行する場合など、非常に大きなデータ セットでは問題となる可能性があります。