如何计算嵌套循环的时间复杂度？附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.")

• 若默认所有用户输入均合法，无需重试：
  最外层while self.rotors == []仅执行1次（执行完3次转子录入后self.rotors不再为空），内层for循环固定执行3次，最内层的输入校验while循环执行0次，整体操作次数是固定常数，大O表示法中常数会被归为O(1)，也就是你提到的O(3)。
• 若统计最坏情况下的用户输入重试次数：
  外层while循环固定执行1次可忽略；设r为单个转子输入的无效重试次数（可变，由用户输入行为决定），整体时间复杂度为O(3×r)，和你提到的O(n×3×r)结论一致，仅这里的n恒等于1可省略。

示例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.")

• 若默认所有用户输入均合法，无需重试：
  外层for循环固定执行3次，内层校验while循环执行0次，整体是固定常数级复杂度，即你提到的O(3)，大O规范写法为O(1)。
• 若统计最坏情况下的用户输入重试次数：
  设n为单个起始点输入的无效重试次数（可变），整体时间复杂度为O(3×n)，大O规范写法可省略常数系数记为O(n)。

额外说明：大O表示法用于描述操作次数随输入规模增长的上界，固定常数系数和常数项都会被省略，因此O(3)本质上等价于O(1)，只有和可变输入规模相关的变量才会保留在表达式中。

内容的提问来源于stack exchange，提问作者User1