算法4 算法分析

分析一个算法的运行时间和内存占用是有必要的,这样我们才能正确的分析出算法不足的地方并加以优化,本文将带你了解分析一个算法的基本方式和步骤。

  1. 统计程序中频率和成本最高的代码,估算算法的时间复杂度;
  2. 每次使用翻倍的数据量测试算法,观察时间的增长率;
  3. 验证时间是否和估算的时间复杂度一致。

时间复杂度:随着问题规模增大,程序计算出结果所需要花费的时间的增长率称为渐进时间复杂度,简称时间复杂度,时间复杂度通常使用近似值表示。

3SUM问题

现在我们来看一个3SUM的案例,给定N个不重复的整数,3个整数相加和为0的组合有多少个?通过暴力计算的方式如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class ThreeSum {

public static int count(int[] a) {
int n = a.length;
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
if (a[i] + a[j] + a[k] == 0)
count++;
return count;
}

public static double timeTrial(int n) {
int max = 1000000;
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = StdRandom.uniform(-max, max);
}
Stopwatch stopwatch = new Stopwatch();
int count = count(a);
return stopwatch.elapsedTime();
}

public static void main(String[] args) {
for (int n = 250; true; n += n) {
double time = timeTrial(n);
StdOut.printf("%7d %5.1f\n", n, time);
}
}
}

算法中成本最高的地方无疑是count()方法中的三层for循环,循环中最昂贵的的操作则是if语句,访问了3次数组。那么我们可以用if语句的总次数作为计算时间复杂度的依据。

计算时间复杂度时,我们通常忽略低阶项和系数,取近似值: ,因为当问题规模足够大时,低阶项的影响微乎其微。而系数也是不需要的,我们把他当做一个常数c看待,这个常数我们不会写进时间复杂度的公式里,因为常数c的存在是公认的。

然后,我们运行算法,观察它的运行时间(秒):

1
2
3
4
5
6
7
8
java-algs4 ThreeSum
250 0.0
500 0.0
1000 0.1
2000 0.8
4000 6.4
8000 51.1
...

16000的测试数据我已经等不下去了,它到底还要运行多长时间?

我们可以把时间和问题规模代入时间复杂度的公式,计算出常数c的值,然后即可预测出16000的测试数据需要运行的时长:

所以,16000个测试数据的ThreeSum程序的运行时间为 408.8秒,和实际运行时间正好匹配。

其实我们没必要计算出常数,更简单的计算方式则是:问题规模增加1倍,运行的时间将增加8倍(2^3 立方级),51.1 * 8 = 408.8。

常用的时间复杂度

大多数情况下,我们不需要做过于详细的数学计算,而是使用时间复杂度对其分类。

例如上面3sum问题有三个嵌套的for循环,所以很容易可以看出它的时间复杂度为 ~

再例如2分查找,因为每次查找后可以将范围减半,所以也很容易得出它的增长数量级为 ~ logN。

log-log plot

时间复杂度通常使用双对数坐标图表示。

下面表格表示对于不同的增长数量级而言,各个年代在几分钟内可以解决的问题规模:

problem size solvable in minutes

关于大O表示法:

现在大多数人喜欢使用 T(N) = O(logN) 这种方式表示算法的渐进时间复杂度,其实某些情况下这是一种错误的表达方式。它表示的是算法的上界,即算法在最坏的情况下的时间复杂度。例如很多人说快速排序的时间复杂度为NlogN,这是正确的,但是不能将它表示为 O(NlogN),因为快速排序实际的上界的~

所以这一系列的算法文章中,我都会使用~符号表示时间复杂度。

内存分析

分析内存的消耗相对简单,因为只需要涉及到相关的声明语句即可,下面是java的常见内存消耗(会因为java版本和系统、硬件等因素而产生差异)。

基本数据类型 bytes
boolean 1
char 2
int 4
float 4
long 8
double 8

对象

对象需要16个字节的对象开销,还会被填充为8的倍数(64位系统)。

1
2
3
4
5
class Date {
int year;
int month;
int day;
}

例如一个date对象,16字节对象开销加上3个4字节int类型 = 28字节,不是8的倍数所以又填充了4个字节,一共32字节的内存消耗。

数组

一个原始数据类型的数组一般需要24字节的头信息(16个字节的对象开销,4个字节记录长度,4个字节的填充)

header 1 header 2
char[] 2N + 24
int[] 4N + 24
double[] 8N + 24

字符串对象

string object memory

长度为N的String对象一般需要使用40个字节(对象本身)加上(24 + 2N)字节(字符数组),总共64+2N字节。

字符串的优化:当调用substring方法时,会创建一个新的String对象(40字节),但是它重用了相同的value[]数组,只是偏移了offset,所以得到的子串只占用40字节。

举例

WQUF memory

使用了 8N + 88个字节, 取近似值8N即可。

挑战:优化3SUM算法

上面使用暴力方式解决3SUM问题用了立方级别的算法,实际上3SUM的时间复杂度可以优化到平方级。

快速2SUM

这里先讲一个如何快速2SUM的例子。如果使用暴力方式,双循环的对两个数字相加,那么它的时间复杂度为平方级。

1
2
3
4
5
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++)
if (a[i] + a[j] == 0)
count++;

假设数组是有序的,我们就有了更优的算法,可从数组两端同时遍历:

1
2
3
4
5
6
7
8
9
10
11
12
13
int lo = a[0], hi = a[n-1];
while(lo < hi) {
int sum = a[lo] + a[hi];
if(sum == 0) {
lo++;
hi--;
count++;
} else if(sum < 0) {
lo++;
} else {
hi++;
}
}

上面的方式将2SUM优化到了线性级(前提是有序的数组)。

应用到3SUM

我们可以将数组进行排序,然后将快速2SUM的原理应用到3SUM中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int optimizeCount(int[] a) {
Arrays.sort(a);
int n = a.length;
int count = 0;
for (int i = 0; i < n; i++) {
int lo = i + 1;
int hi = n - 1;
while (lo < hi) {
int sum = a[lo] + a[hi] + a[i];
if (sum == 0) {
count++;
lo++;
hi--;
}
else if (sum < 0) lo++;
else hi--;
}
}
return count;
}

现在可以分析出,优化后的3SUM算法的时间复杂度为:NlogN + N2,忽略低阶项后为N2,平方级。

然后我们再通过测试验证我们的分析:

1
2
3
4
5
6
7
8
9
10
11
12
$java-algs4 ThreeSum
250 0.0
500 0.0
1000 0.0
2000 0.0
4000 0.0
8000 0.0
16000 0.2
32000 0.7
64000 3.1
128000 12.4
...

平方级的含义:问题规模增大一倍,程序运行时间增加4倍(2^2)。

我们可以简单验证下:0.2 * 4 = 0.80.7 * 4 = 3.2; 3.1 * 12.4 = 3.4; 可以看出问题规模越大,计算出的结果越符合实际运行时间,因为时间复杂度中的低阶项在小规模问题中还是存在一定影响的。

优化后的3SUM对比原本的3SUM算法,原本8000个整数需要51.2秒现在0.1秒都不需要了。