return 语句中 "or" 的时间复杂度

Question

我有以下代码，想计算时间复杂度：

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 语句中有一个 "or"，我该如何继续？

return not solve(n-1) or not solve(n-2) or not solve(n-3)

Answer 1

通常，在谈论时间复杂度时，我们会考虑最坏的情况。在这里，在绝对最坏的情况下，您将为 n-1、n-2 和 n-3.

计算 solve

因此，T(n) = T(n-1) + T(n-2) + T(n-3)

Answer 2

return not solve(n-1) or not solve(n-2) or not solve(n-3)的最差时间复杂度是T(n-1) + T(n-2) + T(n-3)。

最好的是T(n-1)。

因为如果 a 为真，a or b 不会计算 b。

Answer 3

你应该考虑最坏的情况。假设 not solve(n-1) 和 not solve(n-2) return False。在这种情况下，将始终评估 solve(n-3)。

在复杂度方面，与计算相同：

solve(n-1) + solve(n-2) + solve(n-3)

Answer 4

短路是这种情况下的关键概念：

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).

return 语句中 "or" 的时间复杂度

Time complexity with an "or" in return statement

python

recursion

time

complexity-theory

time-complexity