a
長さの並べ替えられた配列n
(昇順)に対する次のランダム化された検索アルゴリズムを検討してください。x
配列の任意の要素にすることができます。
size_t randomized_search(value_t a[], size_t n, value_t x)
size_t l = 0;
size_t r = n - 1;
while (true) {
size_t j = rand_between(l, r);
if (a[j] == x) return j;
if (a[j] < x) l = j + 1;
if (a[j] > x) r = j - 1;
}
}
から無作為に選択されたとき、この関数のビッグ シータ複雑度(上と下の両方で有界)の期待値は?x
a
と思われますがlog(n)
、命令数で実験を行ったところ、結果はlog(n)
(私のデータによると(log(n))^1.1
、結果にさらに適合する)よりも少し速く成長することがわかりました。
このアルゴリズムには正確に大きなシータの複雑さがあると誰かが私に言いました(したがって、明らかlog(n)^1.1
に答えではありません)。それで、それを証明するためのアプローチとともに、時間の複雑さを教えてください。ありがとう。
更新:私の実験からのデータ
log(n)
mathematica による当てはめ結果:
log(n)^1.1
適合結果: