while循环内嵌套for循环的时间复杂度

Question

如果 while 循环内有一个嵌套的 for 循环，如下所示：

while(condition)
   for(i=0; i<size; i++)

每次执行 for 循环时，for 循环的大小都会增加，从 1,2,...,n-1 开始，而 while 循环运行 n-1 次。

也就是说时间复杂度是O(n^3)？

Answer 1

如果每次执行 for 循环时，您的意思是每次while(condition)触发循环的新运行for，那么时间复杂度为。

也就是说，如果您在内部 for 循环内递增计数器，它将递增 =n选择2次。但是因为大 O 表示法中省略了常数因子和低阶项，所以我们可以写成。

为了便于说明，请考虑这个 Python 2.7 实现（我将外while循环 +size增量转换为 for 循环）：

n = 10
counter = 0

for size in range(1, n):
    for i in range(0, size):
        counter += 1
        print i,
    print
print

print "counter =", counter
print "n choose 2 =", (n * (n - 1)) / 2

输出：

0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
0 1 2 3 4 5
0 1 2 3 4 5 6
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 8

counter = 45
n choose 2 = 45

尝试使用不同的n值运行它，看看该公式是否成立。