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

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

一些可能对您有所帮助的注释：

• 时间复杂度计算假设N接近无穷大，这意味着常数无关紧要。 在您的情况下，O（n） 与 O（3n） 相同。
• 在谈论循环时，您可以将循环长度中的时间复杂度相乘。 在您的情况下，从 0 到 3 迭代会给您 *3 因子。 while 循环可能是无限的（假设对手或只是运气不好），因为用户可能会连续输入不会达到停止条件的输入。如果用户总共给出 N 个输入，则每个输入都是

Answer 2

关于时间复杂性，需要注意的一点是变量通常以某种方式与数据/输入相关。因为您是在循环中获得输入，所以在典型意义上，这里没有时间复杂性。此外，考虑示例2的状态。如果start不在自身中。转子，同时将始终评估为真，因此这是最坏的情况O（无穷大）。

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

最后一个注意事项是，在计算时间复杂度时，你会丢弃常数，所以在你的大O中永远不会有一个数字。