问算法时间分析:递归案例的困惑

EN

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

对于那些不知道的人，算法分析通常是指找到函数运行所需时间的顺序。因此，作为一个简单的例子，如果一个函数有2个嵌套的while循环，从1到n，则函数将花费大约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是随机选择的。

让我们取100元。那么，k的最坏可能值是什么(最坏的意思是导致程序运行时间最长的值)？人们最初可能会认为k=100将是最坏的值，因为这将导致这两个递归运行最多次，因为从R1调用n的n的次数很少。R1将被n=97击中，现在在随后的递归中R1或R2可能会被击中(请记住，每次程序运行时都会随机选择k)。如果不是在循环的每个级别，那么很可能至少会在随后的大量递归循环的每个级别上命中其中一个。

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

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