python - 3 递归 T(n) 和主定理的递归

Question

假设我有下面的代码，我的任务是找到递归T(n)及其最差的运行时间。如果 n 是列表的长度，则该值。

在这种情况下，我们有 3 个递归mystery(mylist[:len(mylist)-t-1])，mystery(mylist[t:len(mylist)- 1])和mystery(mylist[:len(mylist)-t-1])。

def mystery(mylist):
   if len(L) <= 1:
       return
   if len(mylist) >= 3:
       t = len(mylist) // 3
       mystery(mylist[:len(mylist)-t-1])
       mystery(mylist[t:len(mylist)- 1])
       mystery(mylist[:len(mylist)-t-1])

对于递归的情况，我的观察是因为递归是在一起的，所以递归是：

T(n) = T(floor(2n/3)) + T(floor(n/3)) + T(floor(2n/3)) = 2T(floor(2n/3)) + T(floor(n/3))

现在这是困难的部分，要弄清楚f(n)，所以我扩展了递归T(n)并且我得到了越来越多的 T(n)s。我怎么能弄清楚f(n)？

对于基本情况，由于第一个 if 语句， T(0) 和T(1)为 1，而T(2) = 0，因为 n=2 时没有 if 语句。

我的评估是否正确？

谢谢！

标签： pythonrecursionlogicrecurrencemaster-theorem

Answer 1

你对基本情况是正确的。您甚至可以将 T(2) 分组。它仍然是 O(1)，因为您至少要评估两个条件语句，实际上没有任何 O(0) 函数调用。

递归中的 f(n) 项只是您在递归情况下在生成递归调用之外所做的所有工作的表达。在这里，您有 O(1)t = len(mylist) // 3语句和评估两个条件语句的 O(1) 成本：O(1) 总共工作。但是，将列表分成三部分以传递给递归调用也有 O(n) 成本。这给出了 f(n) = O(n) + O(1) = O(n)。由此，我们可以将整体递归表示为：

T(n) = 2T(2n/3) + T(n/3) + O(n) if n >=3
T(n) = 1                        otherwise

但是，主定理不适用于这种情况，因为您有递归调用可以处理不同的子问题大小：您不能隔离单个a或b值来应用主定理。对于这样的重复，您可以应用称为Akra-Bazzi 方法的主定理的推广，参数为：

• a1=2, a2=1
• b1=2/3, b2=1/3
• g(n) = n
• h1(n) = h2(n) = 0

按照该方法，求解 p 的 2(2/3)^p + (1/3)^p = 1，然后计算积分：

用 g(u) = u (as g(n) = n) 来确定复杂度等级。

如果您不需要确切的复杂度类，而只想用主定理推导出一个更简单的上限，您可以使用 3T(2n/3) 为运行时确定递归关系的上限>= 2T(2n/3) + T(n/3)：

T(n) <= 3T(2n/3) + O(n) if n >=3
T(n)  = 1               otherwise

然后，您可以使用主定理求解时间复杂度的上限，其中 a=3、b=3/2 和 f(n)= n^c = n^1 导出 Big-O（而不是比 Big-Theta) 复杂性类。