算法优劣的衡量维度：
- 正确性
- 可读性
- 健壮性: 对不合理输入的反应能力
- 时间复杂度: 估算程序指令的执行次数
- 空间复杂度: 估算程序所占的存储空间
时间复杂度一般用大O表示法(Big O)来描述，它表示的是数据规模n对应的复杂度，规则: 忽略常数、系数、低阶，举例如下：
-
9 » O(1)
-
2n+3 » O(n)
-
n^2 + n + 1 » O(n^2)
-
4n^3 + n^2 + n + 1 » O(n^3)
对数阶的细节：
对数阶一般省略底数
1
log2(n) = log2(9) * log9(N) // 其中log2(9)是常数
所以，log2(n)、log9(n) 统称为logn（底数分别为2和9）
常见的时间复杂度度量值:
- O(1)
也叫常数阶
1
2
3
4
5
6
7
// 1 + 4 + 4 + 4 = 14
// ==>O(1)
void test1(int n) {
for (int i = 0; i < 4; i++) {
print("1");
}
}
- O(logN)
也叫对数阶
1
2
3
4
5
6
7
// log2(n)
// ==>O(logn)
void test2(int n) {
while ((n = n /2) > 0) {
print("1");
}
}
- O(N)
也叫线性阶
1
2
3
4
5
6
7
// 1 + 3n
// ==>O(n)
void test3(int n) {
for (int i = 0; i < n; i++) {
print("1");
}
}
- O(NlogN)
也叫NlogN阶
1
2
3
4
5
6
7
8
9
10
11
12
void test4(int n) {
// 1 + 2 * log2(n) + log2(n) * (1+3n)
// 1 + 3*log2(n) + 2 * nlog2(n)
// O(logn + nlogn)
// ==>O(nlogn)
for(int i = 0; i < n; i = i * 2) {
// 1 + 3n
for(int j = 0; j < n; j++) {
print("1");
}
}
}
- O(N2)
也叫平方阶
1
2
3
4
5
6
7
8
9
10
// 1 + 2n + n *(1 + 3n)
// 3n ^2 + 3n + 1
// ==>O(n^2)
void test5(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; i++) {
print("1");
}
}
}
- O(N3)
也叫立方阶
1
2
3
4
5
6
7
8
9
void test6(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int h = 0; h < n; h++) {
print("1");
}
}
}
}
- O(2^N)
也叫指数阶
1
常见于递归，比如递归树
- 多个数据规模的情况
1
2
3
4
5
6
7
8
9
// O(n+k)
void test8(int n, int k) {
for (int i = 0; i < n; i++) {
print("1");
}
for (int i = 0; i < k; i++) {
print("1");
}
}
当数据规模逐渐增大时，各种时间复杂度算法的耗时:
各种时间复杂度的排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) …
算法的优化方向
- 用尽量少的存储空间
- 用尽量少的执行步骤(执行时间)
- 根据情况可以：
空间换时间或者时间换空间
复杂度分析
最好、最坏复杂度
最好时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。
最坏时间复杂度：在最不理想，运气最坏的时候，执行这段代码的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
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;
}
}
return pos;
}
如上述代码所示：
- 最好情况下：数组array的第一个数据为要寻找的值x，那么最好时间复杂度就是O（1）。
- 最坏情况下：直到循环到数组最后一个数据才与x相等。那么最坏时间复杂度就是O（n）。
平均复杂度
然而最好、最坏两种时间复杂度出现的情况都是很少见的。为了更好的评价一段代码的时间复杂度，我们引用平均复杂度这个概念。
平均复杂度的含义就和它的名字一样，是在平均情况下的复杂度。 它把每种情况下的复杂度加起来，然后除以情况的个数，所得的值就是平均复杂度，类似于数学上的均值。
均摊复杂度
复杂度震荡
常规数据结构的复杂度分析
