分析如下算法的时间复杂度，其中(… ) 运行时间为常数

Question

算法 1

1. i ←1
2. while i n ≤
3. for to j i ←1
4. ( …)
5. end for
6. i i ← 2
7. end while

算法 2

1. i ←1
2. while i n ≤
3. for to j n ←1
4. ( …)
5. end for
6. i i ← 2
7. end while

Answer 1

两个算法时间复杂度都是O(n的平方)，但算法1速度更快，循环次数更少
算法1共循环1+2+3+...+n次，共n * (n+1) / 2 ，也就是0.5n平方+0.5n
算法2共循环 n * n次
所以在时间复杂度上算多项式最高阶都是n的平方，但算法1更快