白袍的小行星

算法复杂度分析

字数统计: 862阅读时长: 3 min
2020/09/20 Share

因为计算机的内存和运算速度不是无限大的,所以我们在设计算法的时候必定要考虑算法的运行时间和占用内存,用来评价它们的标准即算法的时间复杂度和空间复杂度。

时间复杂度

时间复杂度所表示的不是真正的时间,而是一种度量工具。我们把算法需要执行的运算次数输入大小的函数来表示,即T(n),下面是定义:

存在常数 c 和函数 f(N),使得当 N >= c 时 T(N) <= f(N),表示为 T(n) = O(f(n))

具体的证明先不涉及,先看怎样得到算法的时间复杂度。

  • 常数项对算法执行需要的时间增长速度影响不大,所以直接忽略,即当T(n)=c,此算法复杂度为O(1),常数项在程序中具体表现为赋值语句,输出语句等

  • 对于次方项,我们直接关注最高次项,如n^3的增长速度肯定是远超于n^2的,同样的,如果最高次项有常数相乘,也直接忽略

用实例来练习一下:

// 1
void aFunc(int n) {
for(int i = 0; i < n; i++) {
cout << "Hello, World!" << endl;
}
}

函数里有一个循环,循环次数为n,而循环体是一句赋值语句,时间复杂度为O(1),那么此循环的时间复杂度为O(1 x n) = O(n)

// 2
void aFunc(int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << "Hello, World!" << endl;
}
}
}

多个循环嵌套,应该由里向外分析,如这例,循环体时间复杂度为O(1),两个相嵌套的循环的次数都是n,那么此函数的时间复杂度为O(1 x n x n) = O(n^2)

// 3
void aFunc(int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << "Hello, World!" << endl;
}
}
for(int j = 0; j < n; j++) {
cout << "Hello, World!" << endl;
}
}

顺序执行的算法,总时间复杂度等于其中最大的时间复杂度,在上面这个函数中,即O(n^2)

// 4
void aFunc(int n) {
if (n >= 0) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("输入数据大于等于零\n");
}
}
} else {
for(int j = 0; j < n; j++) {
printf("输入数据小于零\n");
}
}
}

条件语句,总时间复杂度等于其中时间复杂度最大的路径的时间复杂度,本例中即O(n^2)

// 5
void aFunc(int n) {
for (int i = 2; i < n; i++) {
i *= 2;
printf("%i\n", i);
}
}

循环体内很好确定,关键在于循环的次数。设循环次数为t,那么2^t = n,所以可得到t = log(2)(n),即时间复杂度为O(log n)

空间复杂度

同样,空间复杂度也是一个度量工具,而非程序实际占用的空间,通常用S(n)来定义。

如果算法执行所需临时空间不随着变量的大小而变化,那么算法的空间复杂度为S(n)=O(1),如:

void aFunc(int n){
n++;
}

要是这样:

void aFunc(int n){
int[] m = new int[n]
}

因为它新申请了一段大小为n的空间,所以S(n)=O(n)

CATALOG
  1. 1. 时间复杂度
  2. 2. 空间复杂度