[数据结构与算法]数据结构复杂度分析——级数和循环

数据结构复杂度分析——级数和循环

参考邓俊辉数据结构课程

一、级数

1. 算数级数
   与末项平方同阶
   $Tn=1+2+3+......+n=n(n+1)/2=O(n^2)$

2. 幂方级数
   比幂次高出一阶
   $T_{2}n=1^2+2^2+3^2+......+n^2=n(n+1)(2n+1)/6=O(n^3)$

3. 几何级数
   与末项同阶
   $T_{a}n=a^0+a^1+a^2+......+a^n=O(a^n)$
   $1+2+4+8+......+2^n=O(2^n)$

4. 收敛级数
   各项递减且都是正数，总和不超过一个上界
   $1+1/3+1/7+1/8+1/15+......=O(1)$

5. 调和级数
   $1+1/2+1/3+1/4+1/5+......1/n=O(logn)$

6. 对数级数
   $log1+log2+log3+......+logn=log(n!)=O(nlogn)$

二、循环

1. 没有耦合的二重循环

for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
    O1Operation(i, j);

$O(n^2)$

2. 有耦合的二重循环

for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
    O1Operation(i, j);

$O(n^2)$

3. 递增不为1的二重循环

for (int i = 0; i < n; i++)
for (int j = 0; j < i; j += 2013)
    O1Operation(i, j);

$O(n^2)$

4. 外循环左移一位

for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < i; j++)
    O1peration(i, j);

$O(n)$ 几何级数，最后一项的指数由n的大小确定

关注博主即可阅读全文