我有以下代码,想计算时间复杂度:
def solve(n):
if n == 0 or n == 2:
return True
elif n == 1:
return False
else:
return not solve(n-1) or not solve(n-2) or not solve(n-3)
如果我有这样的东西:
return solve(n-1) + solve(n-2)
至少在我看来是 T(n) = 2T(n-1)。
但是如果我在 return 语句中有一个“或”,我该如何处理呢?
return not solve(n-1) or not solve(n-2) or not solve(n-3)
最佳答案
短路是这种情况下的关键概念:
return not solve(n-1) or not solve(n-2) or not solve(n-3)
如果第一个函数的结果为假,则逻辑或的第一个操作数为真,则不需要评估其他函数(我们已经知道整体结果)。
如果第一个函数的结果为真,那么我们需要评估第二个函数。按照与上面相同的思路,如果第二个操作数的计算结果为真,那么我们就完成了,我们不需要调用第三个函数。
如果前两个函数的结果都为真,那么我们还需要对第三个函数求值,对表达式进行整体求值。
由于我们讨论的是时间复杂度,因此您需要考虑最坏和最好的情况。
- 最佳情况:一次函数调用。时间复杂度:
T(n - 1)
。 - 最坏情况:三个函数调用。时间复杂度:
T(n - 1) + T(n - 2) + T(n - 3)
。
关于python - 返回语句中的时间复杂度为 "or",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53833084/