如何计算嵌套循环的时间复杂度？

Question

我在计算时间复杂度时遇到问题，尤其是在使用 while 循环时：

示例 1：

while self.rotors == []:
      for i in range(3):
          rotor = input("Choose rotor {}: ".format(i + 1))
          while rotor not in range(1, 6):
                print("\nInvalid. You can only choose from 1 to 5 rotors.")

时间复杂度是O(n x 3 x r)还是O(3)？

示例 2：

for i in range(3):
    start = input("Enter the starting point of rotor {}: ".format(i + 1))
    while start not in self.rotors[i]:
          print("\nEnter one alphabet character or a number form 0-9 ONLY.")

时间复杂度是 O(3 x n) 还是 O(3)？

Answer 1

关于时间复杂度需要注意的重要一点是，变量通常以某种方式与 data/input 相关。因为您是在循环内获取输入，所以这里没有典型意义上的时间复杂度。此外，请考虑示例 2 的状态。如果 start 不在 self.rotors 中，则 while 将始终计算为 true，因此最坏情况为 O(infinity).

时间复杂度通常是在假设输入不变的情况下评估的，作为一个除了参数之外不获取任何输入的函数。如果中断条件在循环中一直依赖于用户，时间复杂度就不再是一个有用的指标。

最后要注意的是，在计算时间复杂度时会舍弃常量，因此大 O 中永远不会有数字。

Answer 2

一些可能对您有所帮助的注意事项：

时间复杂度计算假设 N 接近无穷大，这意味着常数无关紧要。在你的情况下 O(n) 与 O(3n) 相同。
说到循环，可以把时间复杂度乘以循环长度。在你的例子中，从 0 迭代到 3 给你 *3 因子。 while 循环可能是无限的（假设有对手或只是运气不好），因为用户可能会不断输入不会达到停止条件的输入。如果用户总共提供了 N 个输入，则每个输入都 << 比 N 多，而你的 O(3n) 与 O(n)
时间复杂度检查你的程序需要多少时间，特别是这里 - 有多少命令。命令可以是一个含糊不清的短语 - 它是一个原子 CPU 命令吗？装配命令？ python 命令？这取决于您的设置

如何计算嵌套循环的时间复杂度？

How to calculate time complexity of nested loop?

python

time-complexity

coding-efficiency