function foo(n)
if n = 1 then
return 1
else
return foo(rand(1, n))
end if
end function
如果最初以 m 作为参数调用 foo,那么调用 rand() 的预期次数是多少?
顺便说一句,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
.
关于algorithm - 随机数递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39134138/