[解決済み】big-O時間複雑度の高いアルゴリズムが低いアルゴリズムより好ましいと思うケースはありますか？

質問

を希望するケースはありますか？ O(log n) よりも時間の複雑さ O(1) 時間の複雑さ？それとも O(n) から O(log n) ?

何か例はありますか？

どのように解決するのですか？

時間計算量Oが大きいアルゴリズムを、小さいアルゴリズムより優先する理由はたくさんあるはずです。

• ほとんどの場合、低いBig-O複雑度は実現が難しく、熟練した実装と多くの知識、そして多くのテストが必要です。
• big-Oは、定数に関する詳細を隠します。 : で実行するアルゴリズムです。 10^5 は、big-O の観点からは 1/10^5 * log(n) ( O(1) 対 O(log(n) ) が、ほとんどの合理的な n の方が性能が良い。例えば、行列の乗算に最適な複雑さは O(n^2.373) が、この定数は非常に高いので、（私の知る限り）どの計算ライブラリも使っていません。
• big-Oは、何か大きなものの上で計算するときに意味があります。もし3つの数値からなる配列をソートする必要があるのなら O(n*log(n)) または O(n^2) のアルゴリズムを使用します。
• 小文字の時間複雑性の利点は、時には本当に無視できるほど小さいことがあります。例えば 例えば、タンゴツリーというデータ構造があります。 を与える。 O(log log N) の時間複雑性を持つが、同じ項目を見つける二分木もある。 O(log n) . 膨大な数の n = 10^20 は、その差はごくわずかです。
• 時間の複雑さがすべてではありません。で実行されるアルゴリズムを想像してください。 O(n^2) を必要とし O(n^2) のメモリが必要です。よりも望ましいかもしれません。 O(n^3) 時間と O(1) があまり大きくない場合は、スペースが必要です。問題は、長い時間待つことはできますが、あなたのアルゴリズムでそれを使用するのに十分な大きさのRAMを見つけることができるかどうか非常に疑わしいということです。
• 並列化は分散型の世界では良い機能です。簡単に並列化できるアルゴリズムもあれば、全く並列化できないアルゴリズムもあります。複雑度の高い1000台のコモディティマシンでアルゴリズムを実行する方が、少し複雑度の高い1台のマシンを使うより意味がある場合もあります。
• <ストライク ある場所（セキュリティ）では、複雑さが要求されることがあります。ハッシュアルゴリズムが非常に高速であることは、誰も望んでいません（他の人がより速くブルートフォースできるからです）。
• 複雑さとは関係ありませんが、セキュリティ関数のいくつかは、次のような書き方をすべきです。 タイミング攻撃防止 . これらはほとんど同じ複雑さクラスのままですが、何かをするときに常に悪いケースを取るように変更されています。その一例が、文字列が等しいかどうかの比較です。ほとんどのアプリケーションでは、最初のバイトが異なる場合、高速にブレークすることは理にかなっていますが、セキュリティでは、悪い知らせを伝えるために、まだ最後まで待つことになります。
• 誰かが低複雑度アルゴリズムの特許を取得し、企業にとってはお金を払うより高複雑度を使った方が経済的です。
• 特定の状況にうまく適応するアルゴリズムもあります。例えば挿入ソートは、平均的な時間-複雑さが O(n^2) は、クイックソートやマージソートより劣りますが オンラインアルゴリズム 他の多くのアルゴリズムが完全な値のリストに対してのみ効率的に操作できるのに対し、(ユーザーの入力として) 受信した値のリストを効率的にソートすることができます。