7

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;
    }
}

から無作為に選択されたとき、この関数のビッグ シータ複雑度(上と下の両方で有界)の期待値は?xa

と思われますがlog(n)、命令数で実験を行ったところ、結果はlog(n)（私のデータによると(log(n))^1.1、結果にさらに適合する）よりも少し速く成長することがわかりました。

このアルゴリズムには正確に大きなシータの複雑さがあると誰かが私に言いました（したがって、明らかlog(n)^1.1に答えではありません）。それで、それを証明するためのアプローチとともに、時間の複雑さを教えてください。ありがとう。

更新：私の実験からのデータ

log(n)mathematica による当てはめ結果：

ログ(n)

log(n)^1.1適合結果:

ログ(n)^1.1

4

2 に答える 2

5

3 者間比較のカウントに切り替えたい場合は、正確な複雑さをお伝えできます。

キーが位置 i にあり、位置 j との比較の予想数を知りたいとします。位置 j が検査されるのは、それが i と j を含む最初の位置である場合に限り、検査されると主張します。ピボット要素は毎回ランダムに一様に選択されるため、これは 1/(|i - j| + 1) の確率で発生します。

合計の複雑さは、sum_{j=1}^n 1/(|i - j| + 1) の i <- {1, ..., n} に対する期待値です。これは次のとおりです。

  sum_{i=1}^n 1/n sum_{j=1}^n 1/(|i - j| + 1)
= 1/n sum_{i=1}^n (sum_{j=1}^i 1/(i - j + 1) + sum_{j=i+1}^n 1/(j - i + 1))
= 1/n sum_{i=1}^n (H(i) + H(n + 1 - i) - 1)
= 1/n sum_{i=1}^n H(i) + 1/n sum_{i=1}^n H(n + 1 - i) - 1
= 1/n sum_{i=1}^n H(i) + 1/n sum_{k=1}^n H(k) - 1  (k = n + 1 - i)
= 2 H(n + 1) - 3 + 2 H(n + 1)/n - 2/n
= 2 H(n + 1) - 3 + O(log n / n)
= 2 log n + O(1)
= Theta(log n).

(log はここでは自然対数を意味します。) 下位項の -3 に注意してください。これにより、最初は比較の数が対数よりも速く増加しているように見えますが、漸近的な動作により、それは横ばいになっています。小さな n を除外して、曲線を再調整してみてください。

于 2013-05-22T15:30:30.943 に答える
2

rand_between一様確率分布からのサンプリングを一定時間で実装すると仮定すると、このアルゴリズムの予想実行時間は Θ(lg n ) です。証明の非公式なスケッチ: の期待値は でrand_between(l, r)あり(l+r)/2、それらの間の中間点です。そのため、二分探索の 1 回の反復と同様に、反復ごとに配列の半分をスキップすることが期待されます (サイズが 2 のべき乗であると仮定)。

より正式には、quickselectの分析から借用すると、ランダムな中間点を選択すると、半分の時間は ¼ nと ¾ nの間にあることがわかります。左部分配列も右部分配列も ¾ n 個を超える要素を持ちません。残りの半分の時間では、どちらにもn 個を超える要素はありません (明らかに)。それが再帰関係につながる

T(n) = ½T(¾n) + ½T(n) + f(n)

ここで、f( n ) は各反復の作業量です。両辺から ½T(n) を引き、両辺を 2 倍すると、

½T(n) = ½T(¾n) + f(n)
T(n) = T(¾n) + 2f(n)

ここで、2f( n ) = Θ(1) = Θ( n ᶜ log⁰ n ) ここでc = log(1) = 0 であるため、T(n) = Θ( n ⁰ lg n ) = Θ(lg n )。

于 2013-05-22T15:04:23.837 に答える