时间戳

首页 > 解决方案 > 如何找到以下递归代码的时间复杂度？

algorithm - 如何找到以下递归代码的时间复杂度？

问题描述

如何推导以下程序的运行时复杂度？

public void function(int n){
   if(n==1) return;
   for(int i=0;i<n;i++){
     function(i)
   }
}

function(4);

我的理解是，

T(n) = n(T(n-1));
T(n-1) = (n-1)(T(n-2))
T(n-2) = (n-2)(T(n-2))

替换n(T(n-1))为后续扩展后，

T(n) = n((n-1)((n-2)(T(n-2))))

这基本上不过是

n*(n-1)*(n-2)...1 = n!

但是，在不同的帖子中，我发现这2^n不是n!。如果我错过了什么，谁能解释我？

标签： algorithmrecursiondata-structurestime-complexity

解决方案

T(n) = n T(n-1)确实会O(N!)- 但它是错误的递归关系function。

循环从i = 0to运行i = n-1，这意味着递归调用是function(0), function(1), function(2)... , function(n-1). 因此递归关系为：

T(n) = T(0) + T(1) + T(2) + ... + T(n-1)

有一个巧妙的技巧可以帮助您解决这个问题。考虑 中的术语T(n-1)并将扩展写在 的旁边T(n)：

T(n)   = T(0) + T(1) + T(2) + ... + T(n-3) + T(n-2) + T(n-1)
                                                      ------
T(n-1) = T(0) + T(1) + T(2) + ... + T(n-3) + T(n-2)

看看这是怎么回事？从另一个中减去一个，只剩下带下划线的项T(n-1)：

T(n) - T(n-1) = T(n-1)
T(n) = 2 T(n-1)

这种递归的替代形式现在可以用与以前相同的方式求解：

T(n) = 2^2 T(n-2)
     = 2^3 T(n-3)
     = 2^4 T(n-4)
     = ...
     = O(2^n)

qed

推荐阅读