長さ の実数の並べ替えられていない配列があるとしNます。正でない最大の数値 を見つけてから、配列内のより小さいy最初の数値 とより大きい最初の数値 を見つけたいと思います。xyzy
これらの値を見つけるために、シーケンシャル検索とバイナリ検索を非漸近的に (つまり、大きな O だけでなく) 理論的に比較したいと思います。次のように述べるのは合理的ですか?
- 順次検索が必要です
0並べ替えの比較、3*N検索の比較 (3 つの連続した検索)。
- 二分探索が必要
2*N*ln(N) ≈ 1.39*N*log_2(N)並べ替えの比較 (クイックソート、平均) 、log_2(N)検索のための比較まで(配列はソートされているため、ソートされた配列内の隣接する値を調べて見つけたらx、z1 回の検索のみy)。
したがって、次の場合にバイナリ検索が高速になると言えますか
1.39*N*log_2(N) + log_2(N) < 3*N
<=>
0 < N < 3.44779
つまり、非常に小さな配列の場合のみですか?