function foo(n)
if n = 1 then
return 1
else
return foo(rand(1, n))
end if
end function
fooがパラメータとして最初にmで呼び出された場合、rand()が呼び出される予想される回数は何ですか?乱数による再帰
BTW、rand(1、n)は、1からnの範囲で一様分布のランダムな整数を返します。
function foo(n)
if n = 1 then
return 1
else
return foo(rand(1, n))
end if
end function
fooがパラメータとして最初にmで呼び出された場合、rand()が呼び出される予想される回数は何ですか?乱数による再帰
BTW、rand(1、n)は、1からnの範囲で一様分布のランダムな整数を返します。
単純な例は、f(2)
を計算するのに必要な呼び出しです。今度はx
とし、x = 1 + 0/2 + x/2
とし、実際に1
とし、確率は1/2
でf(1)
になります。確率は1/2
で、f(2)
になります。方程式を解くとx = 2
となります。
ほとんどの実行時間の再帰分析と同様に、実行時間の再帰式を取得しようとします。したがって
E[T(1)] = 0
E[T(2)] = 1 + (E[T(1)] + E[T(2)])/2 = 2
E[T(n)] = 1 + (E[T(1)] + E[T(2)] + ... E[T(n)])/n
= 1 + (E[T(1)] + E[T(2)] + ... E[T(n-1)])/n + E[T(n)]/n
= 1 + (E[T(n-1)] - 1)(n-1)/n + E[T(n)]/n
E[T(n)](n-1) = n + (E[T(n-1)] - 1)(n-1)
だから、n
> 1のために:
E[T(n)] = 1/(n-1) + E[T(n-1)]
= 1/(n-1) + 1/(n-2) + ... + 1/2 + 2
= Harmonic(n-1) + 1
= O(log n)
また、これは私たちが直感的かもしれないです我々は、ランダムなコールを進めるために期待の直線性を使用することができますn
はf
への呼び出しごとに約半分になるはずですから、期待しています。
また、「確率の高い最悪のケース」も考えられます。このためには、マルコフの不等式を使用するのが簡単です(P[X <= a*E[X]] >= 1-1/a
)。 a = 100
を設定すると、99%の確率でそれが得られます。アルゴリズムは100 * log n
をrand
に呼び出します。
randはまったく呼び出されないので、n = 1 0で期待値はありませんか?この場合重要ですか? – Kolichikov
さて、あなたは 'if n = 1 then'分岐がとられる1回の呼び出しをしなければなりません。 –
@ThomasAhleは、rand()呼び出しの予想される数を質問します。私はあなたの分析が正しいと思う(私はupvoted)、詳細が少し間違っていることを除いて - E(T(1))= 0 –
この宿題はありますか? –
あなたが言及している 'm'変数は何ですか? – Matt
これはhttp://math.stackexchange.com/questions/633459/recursion-with-random-numberの正確な複製です。質問をする前に、検索機能またはGoogleを使用して質問が既に回答済みかどうかを確認してください。 – m69