递归解决方案的 Big-O 复杂度

Question

我有一个简单的递归解决方案如下：

public int countPaths(int x, int y) {

    if(x == 0 && y == 0) {
        return 0;
    } else if(x == 0) {
        return 1;
    } else if(y == 0) {
        return 1;
    } else {
        int count = countPaths(x-1, y);
        count += countPaths(x, y-1);
        return count;
    }
}

这是为了解决书中的以下问题：Cracking the coding interview

想象一个机器人坐在 X × Y 网格的左上角。机器人只能在两个方向上移动：向右和向下。机器人从 (0,0) 到 (X,Y) 有多少条可能的路径？

我正在尝试确定运行时间复杂度，我相信它是 O(x+y)。我通过使用递归树来达到这个目的，例如如果 x=2 和 y=2

这棵树的最大深度是 (x+y) 并且每一步所做的工作是一个常数。所以完成的最大工作是 (x+y) * c 因此运行时间复杂度是 O(x+y)

问题一：我说的对吗？我相信我计算的上限不够严格

问题 2：接下来，如果我要使用记忆化来改善运行时间，从而不再重复计算子问题，那么运行时间复杂度会怎样？ by Big-o change?

Answer 1

虽然树的深度确实是O(x+y)，但是每一层的节点越来越多，决定复杂度的是节点的数量，而不是树的深度。

如果你写下运行次的递归关系，你会得到：

T(0, y) = T(x, 0) = 1
T(x, y) = T(x-1, y) + T(x, y-1) + 1

如果忽略第二个等式中的 +1（这只能使运行时间更好），您将获得与您的代码首先计算的相同函数，即 choose( x+y, y).

对于 x=y，这是中心二项式系数，大约为 4^x/sqrt(pi*x)，即使 x 的值适中，也足以使算法无用。

通过记忆，您需要为 x 和 y 的每个值做固定量的工作，因此复杂度为 O(xy)。

Answer 2

如果您根据计算给定对 (x, y) 的计数所需的加法次数来评估复杂性，您会得到循环

A(x,y) = A(x-1,y) + A(x,y-1) + 1,

和A(x,0) = A(0,y) = 0.

设置A(x,y) = P(x,y) - 1循环变为

P(x,y) - 1 = P(x-1,y) - 1 + P(x,y-1) - 1 + 1,

或

P(x,y) = P(x-1,y) + P(x,y-1),

和P(x,0) = P(0,y) = 1，给出了经典的帕斯卡三角形，

A(x,y) = (x+y)!/(x!y!) - 1.

您还可以使用递归函数调用的次数，

C(x,y) = C(x-1,y) + C(x,y-1) + 2,

和C(0,y) = C(x,0) = 0.

你会通过设置C(x,y) = 2P(x,y) - 2来解决，得到

C(x,y)= 2(x+y)!/(x!y!)-2.

至于渐近复杂度，这没有区别。这并不比 O((x+y)!/x!y!).

更简单

有了记忆，每次评估（x, y>0）只需要一次加法或两次调用，并且假设一个值的 storage/retrieval 时间恒定，总复杂度会更好 O(xy).

Answer 3

根据@Anonymous 的宝贵意见，我们知道递归关系是：

T(x, y) = T(x-1, y) + T(x, y-1) + 1
Abusing (which is ok in Big-O analysis) the notation, let x = y 
T(x, x) = 2 * T(x-1, x) = 2 * 2 * T(x-2, x) = ... = 2 * ... * 2 * T(0, x)
        = O(2^x)

所以运行时间复杂度是

O(2^n) ; where n = max(x, y)

有了memoization，我明白了，谢谢@Anonymous，应该是O(xy)

递归解决方案的 Big-O 复杂度

Big-O complexity of a recursive solution

java

algorithm

recursion

runtime

big-o