0%

复杂度分析

时间复杂度

大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)