0

我有一个关于涉及递归的伪代码算法分析问题的问题。

对于那些不知道的人，算法分析通常是指找出函数运行所需时间的顺序。举个简单的例子，如果一个函数有 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 的机会）渐近运行时间？

4

1 回答 1

1

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

最好的情况是一个非常微不足道的证明，因为初始n可能只是小于 10。

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

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

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

于 2014-02-04T01:39:05.167 回答