共计 3381 个字符，预计需要花费 9 分钟才能阅读完成。
不管是 Android 代码还是数据结构的设计，都涉及到算法的问题，其中时间复杂度是一个 Core，这篇文章我们就一起聊聊时间复杂度的原理！
1、算法效率
虽然随着计算机硬件的迭代更新，运算处理的性能越来越强，但实际上，它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序，我们就需要考虑到“算法的效率”。
衡量算法的“好坏”和“效率”主要由以下两个指标（复杂度）来评估：
✨ 时间复杂度（运行时间）：评估执行程序所需的时间，可以估算出程序对处理器的使用程度。（本篇博文我们重点探讨时间复杂度）✨ 空间复杂度（占用空间）：评估执行程序所需的存储空间，可以估算出程序对计算机内存的使用程度。
2、算法事例
我们通过几个场景引出时间复杂度的概念，以及常见的几种时间复杂度，最后再总结比较它们的优劣！
场景一
生活场景：你买了一箱“牛栏山二锅头”（16 瓶），2 天喝一瓶，全部喝完需要几天？
很简单的算术问题，2 ✖ 16 = 32 天，那如果一箱有 n 瓶，则需要 2 ✖ n = 2n 天，如果我们用一个函数来表达这个相对时间，可以记作 T(n) = 2n。
代码场景：
for(int i = 0; i < n; i++){// 执行次数是线性的
System.out.println(“ 喝一瓶酒 ”);
System.out.println(“ 等待一天 ”);
}
场景二
生活场景：你又买了一箱“牛栏山二锅头”（16 瓶），决定换个法子喝，5 天为一个周期，喝剩下酒的一半，于是第一次喝 8 瓶，第二次喝 4 瓶，那么喝到最后一瓶需要几天？
这个问题其实也很简单，16/2 = 8，8/2 = 4，4/2 = 2，2/2 = 1（还剩一瓶），这不就是对数函数吗？以 2 为底数，16 为真数，得到的对数就是我们需要的答案！我们可以简写为：5log16，如果一箱有 n 瓶，则需要 5logn 天，如果我们用一个函数来表达这个相对时间，可以记作 T(n) = 5logn。
代码场景：
for(int i = 1; i < n; i *= 2){
System.out.println(“ 喝一瓶酒 ”);
System.out.println(“ 等待一天 ”);
System.out.println(“ 等待一天 ”);
System.out.println(“ 等待一天 ”);
System.out.println(“ 等待一天 ”);
场景三
生活场景：酒喝多了，买了一瓶枸杞，3 天喝一瓶，请问喝完枸杞要几天？
是的，你没听错，我只是问你喝完枸杞要多久？答案很简单：3 天！如果我们用一个函数来表达这个相对时间，可以记作：T(n) = 3。
代码场景：
void drink(int n){
System.out.println(“ 喝一瓶枸杞 ”);
System.out.println(“ 等待一天 ”);
System.out.println(“ 等待一天 ”);
场景四
生活场景：酒瘾难戒，又买了一箱好酒（6 瓶），但是又不能多喝，于是第一瓶喝了 1 天，第二瓶喝了 2 天，第三瓶喝了 3 天，这样下去全部喝完需要几天？
不用我说，其实这就是一个 1 + 2 + 3 … + 6 的算术问题，我们知道有个公式：6(6+1)/2 = 21 天，那如果有 n 瓶，就需要 n(n+1)/2 天，如果我们用一个函数来表达这个相对时间，可以记作 T(n) = n²/2 + n/2。
代码场景：
void drink(int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
System.out.println(“ 等待一天 ”);
}
System.out.println(“ 喝一瓶酒 ”);
}
}
3、渐进时间复杂度
有了基本操作执行次数的函数 T(n)，是否就可以分析和比较一段代码的运行时间了呢？还是有一定的困难。比如算法 A 的相对时间是 T(n) = 100n，算法 B 的相对时间是 T(n) = 5n²，这两个到底谁的运行时间更长一些？这就要看 n 的取值了！
所以，这时候有了“渐进时间复杂度”（asymptotic time complectiy）的概念。
我们看看官方的定义：若存在函数 f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。记作 T(n)= O(f(n))，称 O(f(n)) 为算法的“渐进时间复杂度”，简称“时间复杂度”。渐进时间复杂度用大写 O 来表示，所以也被称为“大 O 表示法”。
4、推导原则
如何推导出时间复杂度呢？有如下几个原则：
✨ 1、如果运行时间是常数量级，用常数 1 表示；
✨ 2、只保留时间函数中的最高阶项；
✨ 3、如果最高阶项存在，则省去最高阶项前面的系数。
5、事例再分析
场景一
相对时间：T(n) = 2n，根据推导原则三：最高阶数为 2n，省去系数 2，转换后的时间复杂度为：T(n) = O(n)。
场景二
相对时间：T(n) = 5logn，根据推导原则三：最高阶数为 5logn，省去系数 5，转换后的时间复杂度为：T(n) = O(logn)。
场景三
相对时间：T(n) = 3，根据推导原则一：只有常数量级，用常数 1 表示，转换后的时间复杂度为：T(n) = O(1)。
场景四
相对时间：T(n) = n²/2 + n/2，根据推导原则二：最高阶数为 n²/2，省去系数 0.5，转换后的时间复杂度为：T(n) = O(n²)。
这四种时间复杂度究竟谁用时更长，谁节省时间呢？O(1) < O(logn) < O(n) < O(n²)
6、其他常见复杂度
除了常数阶、线性阶、平方阶、对数阶，还有如下时间复杂度：
f(n)
时间复杂度
阶
nlogn
O(nlogn)
nlogn 阶
n³
O(n³)
立方阶
2ⁿ
O(2ⁿ)
指数阶
n!
O(n!)
阶乘阶
(√n)
O(√n)
平方根阶
7、复杂度比较
n
logn
√n
nlogn
n²
2ⁿ
n!
5
2
2
10
25
32
120
10
3
3
30
100
1024
3628800
50
5
7
250
2500
约 10^15
约 3.0*10^64
100
6
10
600
10000
约 10^30
约 9.3*10^157
1000
9
31
9000
1000 000
约 10^300
约 4.0*10^2567
从上表可以看出，O(n)、O(logn)、O(√n)、O(nlogn) 随着 n 的增加，复杂度提升不大，因此这些复杂度属于效率比较高的算法，反观 O(2ⁿ) 和 O(n!) 当 n 增加到 50 时，复杂度就突破十位数了，这种效率极差的复杂度最好不要出现在程序中，因此在动手编程时要评估所写算法的最坏情况的复杂度。
这些时间复杂度究竟谁用时更长，谁节省时间呢？O(1) < O(logn) < O(√n) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
8、再举一例
????【疑问】????：现在计算机硬件性能越来越强，算法真的体验那么明显吗？算法时间复杂度真的需要那么重视吗？
我相信你肯定存在这样的疑问，虽然我们知道算法这个东西是很重要的，但是我们平常可能接触不多，很多时候计算机的性能已经能满足我们的需求，但是我还是要举个例子让你更直观的看到不同算法之间的巨大差异！
???? 算法 A 的相对时间规模是 T(n) = 100n，时间复杂度是 O(n)，算法 A 运行在老旧电脑上。???? 算法 B 的相对时间规模是 T(n) = 5n²，时间复杂度是 O(n²)，算法 B 运行在某台超级计算机上，运行速度是老旧电脑的 100 倍。
当随着 n 的增大，我们通过表格看看 T(n) 的变化：
n
T(n) = 100n ✖ 100
T(n) = 5n²
1
10000
5
5
50000
125
10
10 0000
500
100
100 0000
50000
1000
1000 0000
500 0000
2000
2000 0000
2000 0000
10000
1 0000 0000
5 0000 0000
100000
10 0000 0000
500 0000 0000
1000000
100 0000 0000
50000 0000 0000
从表格中可以看出，当 n 的值很小的时候，算法 A 的运行用时要远大于算法 B；当 n 的值达到 1000 左右，算法 A 和算法 B 的运行时间已经接近；当 n 的值达到 2000 左右，算法 A 和 算法 B 的运行时间一致；当 n 的值越来越大，达到十万、百万时，算法 A 的优势开始显现，算法 B 则越来越慢，差距越来越明显。这就是不同时间复杂度带来的差距，即便你的计算机很牛 X！
参考博客
一套图 搞懂“时间复杂度”
