基本随机算法复发

问题描述：

我很难完全理解如何为随机算法的预期运行时间编写循环。基本随机算法复发

我相信我做得很对，但如果有人能够查看它，那将是一个巨大的帮助。

下面是该算法的伪代码：

printIntegers(A, n) // an array A of integers is the input, with n integers 
    if A.length > 0 
     for i = 1 to n 
      print A[i] 
     randInt = rand(1, 10) 
     if randInt != 10 
      return 
     else 
      printIntegers(A, n-1)

唯一的随机部分是1到10之间我想明白怎么会在复发翻译随机生成。

我在想：

T(n) = O(n)    if a != 10  probability = 9/10 
     T(n-1) + O(n)   a = 10     = 1/10 
     T(n-2) + O(n) 
     .... 
     T(0) + O(n)

这是有道理的在我的头上，然后预计运行时间为O（N）。我正确地处理这个问题吗？

答

请注意，初始条件应该在检查中使用n，而不是A.length，因为后者在递归中没有变化。

expected递归将被调用的次数为0.1。期望与递归被调用的概率相同。在目前的情况下，如果随机数发生器是真正随机的，则数字10将出现1/10的时间。同样，预期次数不会递归的是0.9。上述

T(n) = (0.9 + 0.1) * O(n) + 0.1 * T(n-1) 
    = O(n) + 0.1 * T(n-1) 
    = O(n) + 0.1 * (O(n-1) + 0.1 * T(n-2)) 
    = O(n) + 0.1 * O(n-1) + 0.1^2 * O(n-2) +... 
    = O(n) * (0.1 + 0.1^2 +...+0.1^(n-1)) + 0.1^(n-1) * T(1) 
    = O(n) * (1 - 0.1^n)/0.9 + K

是O(n * (1 - 0.9^n)/0.9)这基本上取决于你的准确度需要同O(n)：但O(n)考虑期望值时出现在这两种情况下，这样的公式会。

谢谢，你是否介意在不考虑预期值的情况下详述公式？它把我扔了一下。 – rigatoni

解释并修复了一堆错误。 – user1952500

答

首先注意到：

T(n) = n + (n-1)/10 + (n-2)/10^2 + ... + 1/10^{n-1}

然后，边界上面的T（n）的：

T(n) = n + (n-1)/10 + (n-2)/10^2 + ... + 1/10^{n-1} 
    < n + n/10 + n/10^2 + ... + n/10^{n-1} 
    = n(1 + 1/10 + ... + 1/10^{n-1}) 
    < n(1 + 1/10 + 1/10^2 + ...) 
    = n/(1 - 1/10) = 10n/9

和下方包围它：

T(n) = n + (n-1)/10 + (n-2)/10^2 + ... + 1/10^{n-1} 
    > n

所以n < T(n) < 10n/9和T(n)是Theta(n)。

基本随机算法复发

相关推荐