复杂度分析
时间复杂度
渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。
O(1)
常量级的时间复杂度,代码计算规模不随着n增长而增长,如下代码:
int i = 1;
int j = 2;
int sum = i + j;
O(logn)、 O(nlogn)
对数阶时间复杂度比较难分析,可以通过下面的代码看:
int i = 1;
while(i < n) {
i = 2 * i;
}
容易看出,算上面的时间复杂度,主要是算出第 3 行执行了多少次。列出公式:
$2^x = n$
只要求出 x 值,就可以得到时间复杂度,由高中知识可知:
$x = log_2n$
所以,复杂度是O($log_2n$)。
下面我们稍微改下代码:
int i = 1;
while(i < n) {
i = 3 * i;
}
易得时间复杂度是 O($log_3n$)。
因为对数之间是可以互相转换的:
$log_3n = log_32 * log_2n$
$log_3n = C * log_2n$
我们知道在时间复杂度的计算中,常数 C 是可以省略掉的,因此:
O($log_3n$) = O($log_2n$)
所以对数的底可以直接忽略掉,为O($logn$)。
时间复杂度O($nlogn$)就是把时间复杂度为O($logn$)的代码执行 n 次。
O(m + n), O(m * n)
这种类型的时间复杂度由两块代码的数据规模共同决定,他们不是常数,比如:
void cal(int m, int n)
{
int sum1, sum2, i, j;
i = j = 0;
sum1 = sum 2 = 0;
for(i = 0; i < m; i++)
{
sum1 += i;
}
for(j = 0; j < n; j++)
{
sum2 += j;
}
return sum1 + sum2;
}
这里的时间复杂度由 m 和 n 的规模共同决定,故上面代码时间复杂度是 O(m + n)。
稍微改下代码:
void cal(int m, int n)
{
int sum, i, j;
i = j = 0;
sum = 0;
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
sum += i * j;
}
}
return sum;
}
故上面代码时间复杂度是 O($m \times n$)。
最好时间复杂度
最好时间复杂度就是指在最理想的情况下,执行某一段代码的时间复杂度。
最坏时间复杂度
最好时间复杂度就是指在最糟糕的情况下,执行某一段代码的时间复杂度。
例子
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
从上面的代码看,之前我们的时间复杂度就无法进行分析了,因为如果在一开始就找到的需要寻找的元素,直接 break
的话,那么时间复杂度是O(1);如果到数组的最后才找到的话, 那么时间复杂度是O(n)。
平均时间复杂度
但是这两种情况都是最极端的情况,我们需要分析更可能出现的情况的概率,所以这里引入一个新的概念:平均时间复杂度。
还是上面的例子,我们分析,从概率论上说,这个数字找到和找不到的概率都是 $\frac{1}{2}$ ,然后出现在 0 和 n - 1 这 n 个位置上的概率是 $\frac{1}{n}$。所以把各种情况都考虑进去的话, 平均时间复杂度的计算过程变成了:
$1 \times \frac{1}{2n} + 2 \times \frac{1}{2n} + \cdots + n \times \frac{1}{2n} + \frac{n}{2}$
$ = \frac{1}{2n} \times (1 + 2 + \cdots + n) + \frac{n}{2}$
$= \frac{1}{2n} \times \frac{(1+n)\times n}{2} + \frac{n}{2}$
$= \frac{1+n}{4} + \frac{2n}{4}$
$= \frac{3n + 1}{4}$
知道可以忽略复杂度中的系数和常数
O (n) = $\frac{3n + 1}{4} = \frac{3}{4}n + \frac{1}{4} =$ O(n)
上面这个值就是概率论中的加权平均值,也叫做期望值,所以平均时间复杂度的全称叫做加权平均复杂度,或者期望时间复杂度。
空间复杂度
渐进时间复杂度,表示算法的存储空间与数据规模之间的增长关系。
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
这里的空间复杂度只跟第 3 行的 n 有关系,也就是O(n)。就是这么简单,常用的空间复杂度一般有
O(1)、O(n)和O($n^2$)。
总结
越高阶的复杂度,效率越是低下;
时间复杂度从O(1), O($logn$), O(n), O($nlogn$), O($n^2$)依次递增;
空间复杂度一般是O(1)、O(n)和O($n^2$)。
参考文献:
数据结构与算法之美 - 王争