我有以下代码，并想计算时间复杂性：
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)
如果第一个函数的结果是错误的，因此逻辑ORS的第一操作数是正确的，则不需要评估其他功能（我们已经知道总体结果）。
>如果第一个函数的结果为真，则需要评估第二个功能。按照与上述相同的思维方式，如果第二个操作数评估为true，那么我们就完成了，我们不需要调用第三个功能。
如果前两个函数的结果都是正确的，那么我们也需要评估第三个功能，以评估整体表达式。
，由于我们谈论时间复杂性，因此您需要考虑最坏和最佳情况。
- 最佳情况：一个功能调用。时间复杂性：
T(n - 1)。 - 最坏的情况：三个函数调用。时间复杂性：
T(n - 1) + T(n - 2) + T(n - 3)。
您应该考虑最坏的情况。假设not solve(n-1)和not solve(n-2)返回False。在这种情况下，solve(n-3)将始终评估。
在复杂性方面，它与计算相同：
solve(n-1) + solve(n-2) + solve(n-3)
通常，在谈论时间复杂性时，我们会以最差的情况来思考。在这里，在绝对最坏的情况下，您将计算n-1，n-2和n-3的solve。
因此，t（n）= t（n-1） t（n-2） t（n-3）
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 or b如果a为true，则不会评估b。