分母任务递归算法的时间复杂度

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+1)中减去T(n) (去掉常量的标准技巧)，我们得到：

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)

这是一个同素线性递推关系，形式的解也是如此。

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

其中A_i是(复)常数，a_i是方程x^6 = 2x^5 - x^3 +x- 1的根。

因此，T(n)的增长阶为O(a^n)，其中a是方程的最大大小根。这恰好是真的，大约是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)，您可以通过测量递归树中的叶数来证明这一点。