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

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

你说的对，分析的关键有两个。由于您使用 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)，您可以通过测量递归树中的叶数来证明这一点。

Answer 2

您对 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 的根。

因此 T(n) 的增长阶数将为 O(a^n)，其中 a 是方程的最大幅度根。 That happens to be real, and is approximately 1.7049.

因此您的代码运行时间为 O(1.705^n)。这比 O(3^n) 好很多，尽管当然仍然是指数级的。

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

Time complexity of recursive algorithm for denomination task

algorithm

recursion

big-o

swift