含特殊内层循环的Big O notation时间复杂度判定咨询

Case A 分析 #

• 结论：你的推导结果正确，最坏时间复杂度为 O(N)
• 具体计算逻辑：
  外层循环固定执行N次，前N-1次循环仅做常数级条件判断，单次耗时O(1)，总耗时为O(N)；最坏情况下最后1次外层循环触发内层逻辑，内层循环完整执行N次打印操作，耗时O(N)。总操作次数为 (N-1)*1 + 1*N = 2N-1，大O表示法会忽略常数项与常数系数，因此最终时间复杂度为O(N)。
• 误区修正：你提到的两种总次数计算思路都存在表述偏差，既不是n*1，也不是n+n+1，正确的总操作次数计算应为2N-1，最终大O阶不受常数影响，所以你得出的O(N)结果是对的。

Case B 分析 #

• 结论：你的分析完全正确，最坏时间复杂度为 O(N²)
• 具体计算逻辑：
  外层循环固定执行N次，仅i=0时不触发内层循环，剩余N-1次外层循环都会触发完整的内层N次打印操作。总操作次数为 1*1 + (N-1)*N = N² - N +1，大O表示法仅保留最高阶项，忽略低阶项与常数系数，因此最终时间复杂度为O(N²)，你推导的n*(n-1)最高阶为N²，结果符合要求。

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