O递归解决方案的复杂性

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

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;
    }
}

这是解决以下问题的书：破解编码采访

想象一下，一个机器人坐在Y轴上的X左上角。 机器人只能在两个方向上移动：向右和向下。 机器人从（0,0）到（X，Y）的路径有多少？

我试图确定运行时间的复杂性，我相信它是O（x + y）。 我通过使用递归树来解决这个问题，例如，如果x = 2且y = 2

这棵树的最大深度是（x + y），每一步完成的工作是一个常量。 所以最大的工作是（x + y）* c，因此运行时间复杂度为O（x + y）

问题1：我正确吗？ 我相信我计算的上限不够紧

问题2：接下来，如果我要通过记忆来提高运行时间，从而不重复计算子问题，那么Big-o所描述的运行时间复杂度如何改变？

---

虽然树的深度是O（x + y），但每层的节点越来越多，而决定复杂性的节点数量并不是树的深度。

如果您记下运行时的重复关系，则会得到：

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

如果忽略第二个方程式中的+1（它只能使运行时间更好），则可以得到与代码首先计算相同的函数，即选择（x + y，y）。

对于x = y，这是中心二项式系数，大约为4 ^ x / sqrt（pi * x），即使x的中等大数值足够大，也会使算法无用。

通过memoisation，你可以为x和y的每个值做不断的工作量，所以复杂度是O（xy）。

---

如果您根据评估给定对(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 ）只需要一次或两次调用，并且假设用于存储/检索某个值的时间不变，则总复杂性是更好的O(xy) 。

---

基于来自@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） ; 其中n = max（x，y）

随着memoization，我明白了，谢谢@Anonymous，它应该是O（xy）

链接地址: http://www.djcxy.com/p/39335.html

上一篇: O complexity of a recursive solution

下一篇: What's time complexity of this algorithm for Wildcard Matching?