这篇文章收录在我的 Github 上 algorithms-tutorial，另外记录了些算法题解，感兴趣的可以看看，转载请注明出处。
(一) 基本概念
算法性能的好坏一般由内部和外部因素所决定：
- 内部：算法性能，所需要的时间，所需要的内存空间
- 外部：输入信息的大小，计算机的速度，编译器的质量
时间复杂度使用来评判一个算法性能的好坏，主要测量的是算法内部因素, 而常常忽略那些外部因素，或者认为它们是相同的。
那么算法性能的本质是由增长率所决定的，我们一般用符号 O 来进行表示，当输入函数参数个数为 n 是，通过 O 描述算法的性能。
比如一个简单的冒泡排序，我们往往忽略单次比较所花费的时间，而是通过当判断的数目增多时，其判断次数随着数目的变化趋势，也就是所谓的增长率。
(二) 常见的时间复杂度
| 时间复杂度 | 举例 |
|---|---|
| O(1) | 弹出一个栈顶元素 |
| O(logn) | 二分查找 - 平衡树 |
| O(n) | 线性查找 - 乱序查找 |
| O(n^2) | 冒泡排序 |
| O(n^3) | 联立线性方程 |
| O(2^n) | 汉诺塔问题 |
| O(n!) | Travelling salesman |
常见的算法时间复杂度由小到大依次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)
例如：
1.png
由图中我们可以看出，当 n 趋于无穷大时， O(nlogn) 的性能显然要比 O(n^2) 来的高
一般来说，只要算法中不存在循环语句，其时间复杂度就是 O(1)
而时间复杂度又分为三种：
- 最优时间复杂度 (Best-Case)
- 平均时间复杂度 (Average-Case)
- 最差时间复杂度 (Worst-Case)
最差时间复杂度的分析给了一个在最坏情况下的时间复杂度情况，这往往比平均时间复杂度好计算，而最优时间复杂度一般没什么用，因为没人会拿一些特殊情况去评判这个算法的好坏。
(三) 计算时间复杂度
1.对于一些简单的输入输出语句或赋值语句(无循环语句)，近似认为需要 O(1) 时间
比如：
int x = 1;
x++;
2.对于顺序结构，需要依次执行一系列语句所用时间可采用 "求和法则"
比如：
for(int i = 0; i < n; i++){
//do something
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
//do something
}
}
代码中包含两段循环，所以时间计算：n + n^2，所以时间复杂度为 O(n^2)
值得注意的是，下面这段代码：
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
//do something
}
}
对循环次数进行求和会发现: n + (n-1) + ... + 1 = 1/2n^2 + 1/2*n，所以时间复杂度仍为 O(n^2)
3.对于判断条件语句来说，一般是求它的最差时间复杂度
比如：
if(x == 2){
return false;
}else{
for(int i = 0; i < n; i++){
if(j == 0){
return true;
}
}
}
一共花费的时间为 ``1 + n * 1```，所以时间复杂度为 O(n)
4.对数时间复杂度：
当每次操作都能将所需要检测的元素减少一半时(即每次操作，未检测元素减少一半)，这样的时间复杂度为 O(logn)
例如: 二分查找法
在一本英文字典书中找一个单词，因为字典都是按英文首字母升序的，所以我们可以从中间页数开始查找，如果首字母比中间页来的小，则范围就锁定在前半本书，然后在在取前半本书的中间来依次进行判断，直到找到该单词。
从上我们可以得出简化计算时间复杂度的步骤:
- 找到执行次数最多的语句
- 计算语句执行次数的数量级
- 用大O来表示结果
最后需要说明的是：性能并不代表一切。还有一些需要权衡的
- 是否容易进行理解、实现和调试
- 高效地利用时间和空间
所以，最大化性能并不一定可取，但时间复杂度仍然可以很好地比较不同算法之间的性能差异。
网友评论