函数是否存在O(-n)的大O复杂度？附Python代码复杂度分析

• 备考算法时遇到复杂度分析题目，最初猜测函数为O(1)（常数时间复杂度），但存在疑惑：部分场景下更大的输入规模反而对应更短的运行耗时，和常规复杂度的直觉不符。
• 疑惑来源：循环变量初始值和输入长度直接绑定，但while循环的终止阈值是固定常量。举例：输入长度为5的列表时n初始值为5，需要循环的次数远多于输入长度为5^10的列表——后者n初始值更高，离终止阈值更近。

待分析代码 #

def foo(xs: List[int]):
    n = len(xs)
    while n < 10**10:
        n += 1
    return n

大O复杂度的核心判定逻辑是：分析输入规模趋近于无穷大时，算法运行时间的增长上界，有限区间内的耗时波动不会影响渐近复杂度的最终结论。

拆解函数执行逻辑：

• 取输入列表长度赋值给n是固定常数操作
• while循环的终止阈值是固定常量10**10，单次循环仅执行n自增的常量操作：
  • 若输入列表长度≥10**10，循环直接跳过，不执行
  • 若输入列表长度<10**10，循环执行次数为10**10 - len(xs)

你提到的“长度为5的输入比长度为5^10的输入循环次数更多”的现象确实存在，但这一现象仅出现在输入长度小于10**10的有限区间内。当输入规模超过10**10这个固定阈值后，无论输入长度再怎么增大，循环都不会触发，运行时间始终为固定常数，不会随输入规模增长而上升。

最终结论：该函数的时间复杂度为 O(1)。

补充说明：常数时间复杂度不要求所有输入的运行时间完全相等，只要求运行时间存在一个和输入规模无关的固定上界，不会随着输入规模无限增大而变长。

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