数据结构学习篇（4）---算法的时间复杂度
由于现在计算机的储存在硬件上能得到很好的解决，所以时间复杂度较空间复杂度更受关注。
1.1 时间复杂度的概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一 个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。那么对于上面这个代码的时间复杂度为O（N^2）；因为cpu的计算速度非常快，所以就没有必要考虑N取值很小的情况，这种情况讨论不同算法的时间复杂度是没有意义的，因为这时他们都属于同一个层次，看不出差别，所以只针对N很大的情况才有时间复杂度这一说法，以此用来计算算法属于哪个量级。
从这个例子就可以看出，对于N=10000000的循环操作，在release版本下的运行时间甚至达不到0ms（比0ms还短的时间），这也就看出只有在N的取值很大情况下才能讨论时间复杂度。
1.2 大O的渐进表示法
本质：用于表示算法的时间复杂度（执行次数）属于哪个量级。
- 常数量级：统一用O（1）表示
- 非常数量级：用表达式中的最高项表示，如:O（N^2）;如果最高项包含系数，要去除系数，因为提到时间复杂度的N值肯定是非常大的，有无系数都不影响N是一个很大的值，所以没有必要加上系数。（用数学中趋近于无穷的角度去看待这个问题）
注：对于涉及到对数的复杂度时，logN指的是以2为底的对数，这里的2被省略了，但是如果底数为其他数字则不能省略。
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
- 最坏情况：任意输入规模的最大运行次数(上界)
- 平均情况：任意输入规模的期望运行次数
- 最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x：
- 最好情况：循环1次找到
- 最坏情况：循环N次找到
- 平均情况：循环N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
1.3 例题分析
例题1：
- 思路1：先排序，再依次查找，如果下个值不等于前一个值加1，那么下一个值就是消失的数字。如果使用冒泡排序，时间复杂度为O（N^2）;如果使用快速排序，时间复杂度为O（N*logN），都不满足题目要求
- 思路2：计算出完整数组中的总数值之和，如何减去nums数组中的每个数值，剩下的数值就是消失的数字，时间复杂度为O（N）。
- 思路3：利用异或的性质：相同为0，不同为1来解决问题，时间复杂度为O（N）
例题2：
- 思路1：暴力解法：依次将数组末尾的数字移到最前端。
说明：这里的k和N（元素个数）是存在关系的：当k除以N的余数不为0时，说明是要进行轮转操作的，当余数为0时，说明不需要进行轮转操作：
- 最好情况：k%N=0：不需要进行轮转
- 最坏情况：k%N=N-1：需要进行的最大轮转次数为N-1
所以这个思路的时间复杂度为O（K*N）=O（N^2）,显然不满足要求
- 思路2：
很显然，时间复杂度为O（N），满足要求。
1.4 更为复杂的复杂度分析
上面两个例题其实可以直接通过循环的次数看出时间复杂度为多少，但是对于一些更为复杂的循环，是不能单纯通过看循环次数就算出时间复杂度的，而是要通过算法的本质思想去计算相应的时间复杂度。
比如这个二分查找算法：
单纯通过看循环次数并不能直接得出时间复杂度为多少，要从算法思想的角度去计算：
所以对于这个算法的时间复杂度就是O（logN）。
补充：二分查找相对于暴力解法来说能大大降低时间复杂度：
但是二分查找也存在一定的缺点：
- 要先进行排序才能进行二分查找；
- 二分查找属于数组结构，不方便进行数据插入或删除。