複雑さ log2(n)/5 のソートされた配列で検索するためのアルゴリズムをコーディングしました。役に立ちますか?
2159 次
5 に答える
12
比較操作のみを想定した検索では、O（log（n））より低くなることはできないことを証明できます。log2（n）/ 5の複雑さは、O（log（n））と同じです。
有用性は、それを何に使用するかによって異なります。
于 2009-02-13T06:33:43.003 に答える
4
うーん。厳しい質問。あなたのアルゴリズムを投稿して、あなたが何をしているか見てみましょう。
ただし、実際に勝つためには、O(log2 log2 (n))? よりも優れている必要があります。それが補間検索が平均して行うことです..
于 2009-02-13T13:39:33.463 に答える
2
配列がソートされていること以外に、配列に関する他の仮定がなければ、または事前計算/データ構造の作成がなければ、log₂n よりも優れた結果を出すことはできません。
探している要素が配列にない場合、どのように log₂n ステップ未満で終了することを提案しますか?
于 2009-02-13T06:57:07.267 に答える
1
もちろん、非線形検索が線形検索よりも必然的に速いかどうかについては、いつでも議論できます: http://www.ddj.com/184405848
つまり、キャッシュ ラインを検索する場合は、分岐よりも直線的に検索する方が高速な場合があります。
于 2009-02-13T07:01:59.313 に答える
1
実際には他の既存の O(logn) 検索アルゴリズムよりも高速であると便利だと思います。つまり、ベンチマーク テストで速度の向上が見られた場合です。ただし、非常に大きな入力の一定時間の改善 (1/5 など) の場合、大きな違いはありません。そのため、アルゴリズムの漸近的な複雑さが最も重要視されます。
于 2009-02-13T13:47:26.033 に答える