时间复杂度和空间复杂度分析技巧

一、算法效率度量

如何度量一个算法的执行效率/时间呢？可以利用计算机的计时功能，来度量算法执行效率高低。这种方法也叫事后统计法。

事后统计法有很大的局限性：

1. 测试结果依赖环境：不同的处理器、不同的操作系统等都会影响测试结果；即使是同一台物理机，Cpu使用率不一样也测试结果也可能不同。
2. 测试结果受数据规模大小影响：数据规模的大小，直接决定了程序的运行时间。

通常分析一个算法效率优劣，不需要计算出具体的执行时间，而是粗略的预估算法的时间效率。

也就是时间复杂度分析方法。

二、时间复杂度

T（n） = O（f（n））

T（n）表示算法的执行时间，n表示数据规模。随着规模n的增大，算法执行时间的增长率和f（n）的增长率相同。叫做算法的渐进时间复杂度，简称时间复杂度。

大O表示算法的执行时间T（n）与f（n）成正比。

如何理解时间复杂度

1. 它表示代码的执行时间随数据规模的增长趋势，不是具体的执行时间。
2. 通常只是表示数据规模n很大时候的执行效率

如何计算时间复杂度

1. 忽略常量、低阶、系数，只保留最高量级。
2. 总得时间复杂度等于量级最大的那段代码的时间复杂度。
3. 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

几种常见的时间复杂度

1. O（1）常量级：哈希表上的各种操作
2. O（logn）对数级：二分查找、调表
3. O（n）线性：数组、链表的遍历
4. O（nlogn）快速排序、归并排序
5. O（n^2）冒泡、插入、选择排序
6. O（2^n）指数级：回溯穷举算法，例如八皇后问题
7. O（n！）：求全排列

最好、最坏、平均时间复杂度

例如：在一个数组中，找到值等于X的数据。我们需要遍历数组，依次每个元素equas寻找X。

1、最好情况的时间复杂度就是O（1）。（接口的最小响应时间）

2、最坏情况时间复杂度O（n）。（接口的最大响应时间）

3、平均时间复杂度： O（n）。（接口平均响应时间）

大多数情况下，平均时间复杂度，就是最差情况的时间复杂度。

4、均摊时间复杂度：是一种特殊的平均时间复杂度。常见的就是支持动态扩容的一些数据结构。

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系。

摊还分析法：这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。

在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

三、空间复杂度

空间复杂度，是度量算法运行过程占用的存储空间，通常使用S（n）表示，n表示问题的规模。

S(n) = O(f(n))

常见的空间复杂度：O（1）、O（n）

1. 空间复杂度 O(1)

代码中m、n所分配的空间都是常量级的，记作O（1）

int m = 1;
int n = 2;

2. 空间复杂度 O(n)
   代码中使用array数组保存变量，随着n的增大，数组所占用的内存也随之增加。记作O（n）

int[] array = new int[n]
for(i=0; i<n; ++i)
{
   array[i] = i;
}