面额任务递归算法的时间复杂度

Question

我计算1,2或5个数字的输入数k的所有可能变体。这是理解的简单算法：

//1,2,5 
func foo(k: Int, result: [Int] = []) { 
    if k == 0 { 
     print(result) 
     return 
    } 

    var one = result 
    one.append(1) 
    foo(k: k-1, result: one) 

    if k >= 2 { 
     var two = result 
     two.append(2) 
     foo(k: k-2, result: two) 
    } 

    if k >= 5 { 
     var five = result 
     five.append(5) 
     foo(k: k-5, result: five) 
    } 
} 

所以，它的工作原理。我的问题是这个算法的复杂性（大O）是什么？ 我认为它是3^k，因为里面有3次递归调用。 请证明或解释你的意见。

Answer 1

你对O（3^n）的分析是正确的，但它不是一个紧密的界限，因为尽管分支因子是（大部分）3，右分支（n-5）的高度小于中间值n-2）和左（n-1）分支。

描述你的代码的递推关系是：T(n) = T(n-1) + T(n-2) + T(n-5) + 1

减去T(n)T(n+1)（标准招摆脱固定的），我们得到：

T(n+1) - T(n) = T(n) + T(n-1) + T(n-4) + 1 - T(n-1) - T(n-2) - T(n-5) - 1 
T(n+1) = 2T(n) - T(n-2) + T(n-4) - T(n-5) 

This is a homogoneous linear recurrence relation, so has solutions of the form：

sum(A_i * a_i^n for i=0..5) 

其中A_i是（复数）常数，a_i是等式的根x^6 = 2x^5 - x^3 + x - 1.0因此，T（n）的增长顺序为O（a^n），其中a是方程的最大量级根。 That happens to be real, and is approximately 1.7049。

所以你的代码运行在O（1.705^n）时间。这比O（3^n）好得多，尽管当然还是指数级的。

Answer 2

你说得对，分析有两个关键。既然你k作为它的参数定义函数，然后让我们写下的k在条款的复杂性：

对于k >= 5，FOO解决大小k的问题归结为一个自称3次，以解决小题，每小题大小k - c，其中c是一个常数（在你的情况下最多5）。因此，你可以记下foo的时间复杂度为：

3 * f(k-1) >= f(k) >= 3 * f(k-5) 

和解决方案显然是f(k) = O(3^k)，这可以证明，例如通过测量递归树叶的数量。