算法时间分析 : Recursion Case Puzzle

Question

我有一道涉及递归的伪代码算法分析题。

对于那些不知道的人来说，算法分析一般是指找到函数运行所需时间量的顺序。因此，举一个简单的例子，如果一个函数有 2 个从 1 到 n 的嵌套 while 循环，则该函数将花费大约 n^2 时间。这对于确定程序运行所需的估计时间非常有用。希望这是有道理的。

这是一个涉及递归的有趣问题。让我们从代码开始:

Func3(A,n) {
    if(n <= 10) then return (A[1])
    k = Random(n); //Random returns a number <= n
    s = A[k]; //A constant time operation (negligible amount of time)
    if(k is even) then s = s + Func3(A,n-3); //Referred to as R1 below.
    if(k <= n/2) then s = s + Func3(A,n-9); //Referred to as R2 below.
    return(s);
}

这是一个有趣的问题，因为您必须仔细考虑 k 的可能性以及 k 是随机选择的事实。

假设 n = 100。那么，k 的最坏可能值是多少(最坏意味着导致程序运行最长时间的值)？一开始可能会认为 k=100 将是最差的值，因为它会导致两个递归运行的次数最多，因为从 R1 调用 n-3 的 n 的数量很少。 R1 将以 n=97 命中，现在在随后的递归中有更多的可能性命中 R1 或 R2(请记住，每次程序运行时都会随机选择 k)。在随后的大规模递归循环的每一级中，至少有一个可能会被击中，如果不是在循环的每一级都被击中的话。

但是，这只会导致其中一个递归运行，而另一个被忽略。也许另一个最坏的情况是 k = 50，正好是 n 的一半， 是偶数。然后，R1 和 R2 都在第一次运行时被击中。这不仅立即花费了两倍的时间，而且现在两个递归都在运行，因此在随后的循环中有两倍的可能性进一步递归。例如，再次取 n = 100 和 k = 50。然后 R1 和 R2 分别命中 n = 97 和 n = 91。然而，现在我们有 2 个递归循环，因此有两倍的可能性进一步递归调用被命中(想想:如果对于随机选择，在那些 R1/R2 递归调用中 K1 = 97 和 K2 = 40 会发生什么从原来的运行中调用？)。

此处计时的最坏情况是什么？ 估计(使用概率，即 R1 = 1/2 的机会，而 R2 = 1/2 的机会)渐近运行时间是多少？

Answer 1

最好的情况是O(1)，最坏的情况是O(n)。

最好的情况是一个非常简单的证明，因为初始的 n 可能刚好小于 10。

最坏的情况并不难证明。基本上，您必须意识到这里的每个操作都与您选择的 n 成正比。 k 为偶数或小于 n/2 的概率都是 O(an) 的形式，因为常量不会实际上很重要，它只是 O(n)。

之后，这只是一个游戏，看你的数字有多快接近小于 10 的数字。由于您要减去常量，并且这两个条件不依赖于 n 的大小，因此它们也必须是 O(an) 的形式。由于在大 O 表示法中未考虑常量，因此您不可能比 O(n)

做得更糟

如果您有任何问题，请告诉我。