python - 返回语句中带有“或”的时间复杂度

我有以下代码，希望计算时间复杂性：

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

如果第一个函数的结果是假的，因此逻辑OR的第一个操作数是真的，那么其他函数不需要被评估（我们已经知道总体结果）。
如果第一个函数的结果是真的，那么我们需要评估第二个函数。按照同样的思路，如果第二个操作数计算为真，那么我们就完成了，我们不需要调用第三函数。
如果前两个函数的结果都是真的，那么我们也需要对第三个函数进行评估，以全面地评估表达式。
因为我们谈论时间复杂性，你需要考虑最坏的情况和最好的情况。
最佳情况：一个函数调用。时间复杂度：T(n - 1)。
最坏情况：三个函数调用。时间复杂度：T(n - 1) + T(n - 2) + T(n - 3)。