python - 返回语句中的时间复杂度为 "or"

标签 python recursion time time-complexity complexity-theory

我有以下代码,想计算时间复杂度:

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/

相关文章:

javascript - 尾递归reduce函数返回[..., [Circular] ]

java - 拼图碎片的排列

ruby-on-rails - 时区困惑(1小时)

python - 如何在应用函数上连接 sum 并将数据帧打印为文件中的表格格式

python - 如何为我控制的 DateTime 编写 sleep 函数?

python 在 xml 文件中编码'(引用)

python - instance'__dict__ 的关键字参数拆包有哪些陷阱?

java - 递归排序日期时出现 StackOverflowError

MySQL 日期时区输入

Python:如何在每次调用时更新变量的值?