数据结构和算法本质就是帮我们用最快的时间和最少的空间来执行我们的代码。所以，执行效率是衡量一个算法的非常重要的指标。那如何来计算你的算法代码的执行效率呢？这就需要时间、空间复杂度来分析了。
有人可能会说，我把代码执行一遍，然后通过统计、监控就能知道执行的时间和需要的内存大小。干嘛还需要时间、空间复杂度来分析呢？我都能得到具体需要的时间和内存了，还需要多此一举吗？
首先，这种评估算法效率的方法没有问题，我们还给这种方法起了一个名字，叫事后统计法。但是这种方法有很大的局限性。
1. 测试结果受测试环境影响
测试环境的硬件对测试结果有非常大的影响。比如，同样的代码在i7和i5的机器上执行，结果肯定是不同的。还有可能在一台机器上A代码比B代码执行速度要快，我们换另外一台机器却得到相反的结果。
2. 测试结果受数据规模的影响
比如排序算法，原始数据如果有序度不一样，执行的时间就会有很大的差别。原始数据规模的大小不同，也可能会让原来速度快的算法变成速度慢的。
所以我们就需要一个不需要具体的测试数据来测试，就可以大概估算出执行效率的方法，就是时间、空间复杂度分析方法。
大O复杂度表示方法
我们通过度代码，来估算出它执行所需要的时间，下边来看一段具体的代码。
public int Function(int n)
{
int sum = 0;
for(int i = 1; i <= n; i++)
{
sum += i;
}
return sum;
}
这里我们假设每一行代码执行的时间都是相同的为 t，那么第 3 行执行的时间为 t，第 4 和 6 行执行了 n 次，需要时间为 2nt，总的时间为 (1+2n)t，可以看出来总的代码的执行时间 T(n) 与每行代码的执行次数成正比。
然后我们再来看下边的代码
public int Function(int n)
{
int sum = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++
{
sum += i*j;
}
}
return sum;
}
这段代码中在上边的基础上又套了一层 for 循环，第 6 和 8 行执行了 n^2 次，需要的时间为 2n^2 * t ,总的需要的时间为 T(n)=(2n^2+2n+1) * t
通过上述两个具体的代码例子我们总结出一个公式：
T(n)=O(f(n))
T(n) 表示代买执行的时间，n 是数据的大小，f(n) 表示代码执行的总次数，O 表示公式中 T(n) 与 f(n) 成正比。这就是大 O 时间复杂度表示法，它实际上并不表示代码具体执行所需要的时间，它表示随着数据规模的变化代码执行时间的变化趋势。
当 n 非常大时，低阶、系数、常量对结果的影响就非常小了，所以我们可以把这几项忽略不记，只保留最高阶的就可以了，所以上边两个例子中 O(1+2n) 就可以记为 O(n)，o(2n^2+2n+1) 就可以记为 O(n^2)。
上边我们知道了怎么用大 O 时间复杂度的表示方法。那么我们如何具体分析一段代码的时间复杂度呢？
- 只关注循环次数最多的一段代码
因为大 O 时间复杂度只表示一种变化的趋势，所以我们只需要关心阶数最高的那部分就可以了，低阶、系数、常量我们都可以忽略。以上边第一段代码为例 O(1+2n)，我们忽略掉系数和常量最后就得到了 O(n)。
- 加法法则
对于顺序执行的长代码，我们把它分成几部分，分别求出其总时间 T(n) ,然后相加得到总的时间，最后同样忽略低阶、系数、常量部分，保留最高阶的部分然后得出最后的时间复杂度大 O。
- 乘法法则
对于逻辑复杂的嵌套代码，我们分别求嵌套内外代码的复杂度，然后相乘得出最终的时间复杂度大 O。
几种常见的时间复杂度分析
下边列举出常见的时间复杂度量级
| 多项式量级 | 非多项式量级 |
|---|---|
| 常数阶 O(1) | 指数阶 O(2^n) |
| 对数阶 O(logn) | 阶乘阶 O(n!) |
| 线性阶 O(n) | |
| 线性对数阶 O(nlogn) | |
| k次方阶 O(n^2) O(n^3) O(n^k) |
对于非多项式量级的算法会随着数据规模的增大急剧增加，所以分多项式量级的算法是非常低效的，我们不做过多的介绍。主要来介绍几种常见的多项式量级的时间复杂度。
- 常数阶 O(1)
O(1) 只是常量级时间复杂度的表示方式，不是只有一行代码，而是每一段代码的执行时间不随着 n 的数据规模的变大而变长，这样的代码的时间复杂度记为 O(n)。
- 对数阶 O(logn) O(nlogn)
对数阶复杂度很常见，但是分析的时候却不容易，下面我们用一段实际的例子来看看对数阶时间复杂度。
public void Function(int n)
{
int i = 1;
while(i<=n)
{
i = i*2;
}
}
通过上边我们总结的方法，我们只需要知道 while 循环的次数，就能得到这段代码的复杂度。从代码中可以看出 i 的值从 1 开始，每循环一次乘以 2，直到 i 的值大于 n 的时候结束，我们得到规律然后把结果列出来，
2^0 2^1 2^3 2^4 …… 2^x = n ，然后求得执行的次数 x = logn ,这段代码的时间复杂度就是 O(logn)。
- O(n+m) O(n*m)
我们再来讲一种跟前面都不一样的时间复杂度，代码的复杂度由两个数据的规模决定，所以我们需要同时考虑两种数据规模对结果的影响，如果是顺序的，那么时间复杂度就为 O(n+m)，如果为嵌套的那么时间复杂度为 O(n*m)。
空间复杂度分析
理解了上边的时间复杂度的分析方法，空间复杂度的分析也就很简单了。空间复杂度表示算法的存储空间与数据规模之间的增长关系。
同样我们通过一段实际的代码来分析一下。
public void Function(int n)
{
int i = 0;
int[] a = new int[n];
for(i;i<n;i++)
{
a[i] = i*i;
}
}
我们看到第 3 行代码，我们申请了一个空间存储变量 i ，但是这个是常数阶的，不会随 n 的变化而变化，所以可以忽略，第 4 行我们申请了一个大小为 n 的 int 类型数组，除此之外其余代码没有占用其他的空间，所以这段代码的空间复杂度为 O(n)。
我们常见的空间复杂度有 O(1)、O(n)、O(n^2)，对数阶的空间复杂度一般情况下用不到。所以空间复杂度比时间复杂度容易分析的多，我们也只需要掌握常见的几种就可以了。
最后我们总结一下常见的几种复杂度，执行效率从高到低依次为
O(1)>O(logn)>O(n)>o(nlogn)>O(n^2)
欢迎关注公众号：「努力给自己看」
公众号200x200
网友评论