两个Python独立循环程序的时间复杂度判定咨询

已知案例 #

• 以下单循环代码的时间复杂度为 O(n)：

n = 10
for x in range(0,n): 
    print("")

• 以下嵌套循环代码的时间复杂度为 O(n²)：

n = 10
for x in range(0,n): 
    for y in range(0,n):
        print("")

问题解答 #

1. 两个独立O(n)循环的程序时间复杂度 #

对于包含两个独立O(n)循环的程序：

# program 1
 
n = 10
for x in range(0,n): 
    print("")

for y in range(0,n): 
    print("")

整个程序的时间复杂度是 O(n)。大O表示法关注的是n趋近于无穷大时的增长趋势，O(n + n)等价于O(2n)，常数系数在大O分析中会被忽略，因此最终简化为O(n)。

2. 独立O(n²)与O(n³)循环的程序时间复杂度 #

对于包含一个O(n²)循环和一个O(n³)循环的程序：

# program 2

n = 10
for x in range(0,n): 
    for y in range(0,n): 
        print("")

for a in range(0,n): 
    for b in range(0,n): 
        for c in range(0,n): 
            print("")

整个程序的时间复杂度是 O(n³)。大O表示法只保留增长速度最快的项，当n足够大时，n³的增长幅度远超过n²，因此n²项可以被忽略，O(n² + n³)最终简化为O(n³)。

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