基本随机算法递归

Question

我无法完全理解如何为随机算法的预期运行时间编写循环。

我相信我做的是正确的，但如果有人可以查看它，那将是一个巨大的帮助。

算法的伪代码如下：

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)。我的做法正确吗？

Answer 1

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

递归调用的 expected 次是 0.1。期望与调用递归的概率相同。在当前情况下，如果随机数生成器是真正随机的，则数字 10 将出现 1/10 次。同样，没有递归的预期次数是 0.9。但是 O(n) 出现在这两种情况下，所以当考虑 预期值 时，等式将是：

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)基本相同，具体取决于您的精度需求。

Answer 2

首先要注意的是：

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)。

基本随机算法递归

Basic randomized algorithm recurrence

algorithm

random

time-complexity

asymptotic-complexity

recurrence