递归解决方案的 Big-O 复杂度
Big-O complexity of a recursive solution
我有一个简单的递归解决方案如下:
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?
虽然树的深度确实是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)。
如果您根据计算给定对 (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)
.
根据@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)
我有一个简单的递归解决方案如下:
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?
虽然树的深度确实是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)。
如果您根据计算给定对 (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)
.
根据@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)