复杂度分析

数据结构与算法｜Algorithm

时间复杂度

大O表示法

1
2
3
4
5
6
7
8
9
int cal(int n) 
{    
    int sum = 0;    
    int i = 1;    
    for (; i <= n; ++i) {      
        sum = sum + i;    
    }    
    return sum;
}

一行代码执行的时间为unit_time
第4行第5行分别执行了n遍，所以是 2*n unit_time

T(n) = O(f(n))
T(n)表示代码执行的时间；n表示数据规模的大小；f(n)表示每行代码执行的次数总和。因为这是一个公式，所以用f(n)来表示。公式中的O，表示代码的执行时间T(n)与f(n)表达式成正比。

时间复杂度分析

  1. 只关注执行次数最多的一段代码
  2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

最好、最坏时间复杂度

1
2
3
4
5
6
7
8
9
10
11
int find(int[] array, int n, int x) 
{   
    int i = 0;   
    int pos = -1;   
    for (; i < n; ++i) 
    {     
        if (array[i] == x) 
        pos = i;   
    }   
    return pos; 
}

代码中时间度复杂度会因为x在不在数组中变化，如果x在数组中则O(n)=1,否则O(n)=n。

平均时间复杂度

要查找的变量x在数组中的位置，有n+1种情况：在数组的0～n-1位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以n+1，就可以得到需要遍历的元素个数的平均值：

$$
\frac{1+2+3+\cdots+n+n}{n+1}=\frac{n(n+3)}{2(n+1)}
$$

考虑到在数组里和不在数组里的概率，以及出现在每个位置的概率，实际上应该是
$$
\begin{aligned} & 1 \times \frac{1}{2 n}+2 \times \frac{1}{2 n}+3 \times \frac{1}{2 n}+\dots+n \times \frac{1}{2 n}+n \times \frac{1}{2}\ = &\frac{3 n+1}{4} \end{aligned}
$$

用大O表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是O(n)。

均摊时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// array表示一个长度为n的数组 
// 代码中的array.length就等于n  
int[] array = new int[n];  
int count = 0;   
void insert(int val) 
{     
    if (count == array.length) 
    {        
        int sum = 0;        
        for (int i = 0; i < array.length; ++i) 
        {           
            sum = sum + array[i];        
        }        
        array[0] = sum;        
        count = 1;     
    }     
    array[count] = val;     
    ++count;  
}

$$
1 \times \frac{1}{n+1}+1 \times \frac{1}{n+1}+\dots+1 \times \frac{1}{n+1}+n \times \frac{1}{n+1}=O(1)
$$

每一次O(n)的插入操作，都会跟着n-1次O(1)的插入操作，所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是O(1)。

思考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10]; 
int len = 10; 
int i = 0; 
// 往数组中添加一个元素
void add(int element) 
{    
    if (i >= len) // 数组空间不够了 重新申请一个2倍大小的数组空间
    {          
        int new_array[] = new int[len*2];      
        // 把原来array数组中的数据依次copy到new_array      
        for (int j = 0; j < len; ++j) 
        {        
            new_array[j] = array[j];      
        }      
        // new_array复制给array，array现在大小就是2倍len了     
        array = new_array;      
        len = 2 * len;    
    }    // 将element放到下标为i的位置，下标i加一   
    array[i] = element;   
    ++i; 
 }

时间复杂度：
最好：O(1)
最坏：O(n)
均摊：O(1) 因为前N个操作都是O(1),最后一个均摊到前n个

空间复杂度：
最好：O(1)
最坏：O(n)