共计 12299 个字符，预计需要花费 31 分钟才能阅读完成。
摘要：复杂度剖析次要就是工夫复杂度和空间复杂度。
本文分享自华为云社区《用艰深的语言解说复杂度》，作者：龙哥手记。
复杂度剖析
刚刚我说过，在俺看来，复杂度剖析是数据结构和算法中最重要的知识点，当然学这篇只是把门找到，反之，学不会它，你就永远找不到火门。
为什么复杂度剖析会这么重要？
这个要从宇宙大爆炸，呃，从数据结构与算法的自身说起。
我平时白天做梦的时候，总想着当当咸鱼，最好能带薪拉屎就能赚大钱那种，数据结构与算法尽管没有俺这么高大尚的幻想，然而它的呈现也是跟我一样总想在更少的工夫及更少的存储来提高效率呗。
能够从哪些方面来动手呢铁子们，CPU 与 RAM 的耗费工夫啊，通信的带宽工夫啊，指令的数量啊，这么多，我不学了不学，没事呀，咱们能够总结一套模型在实践上针对不同算法的状况得出对应规范，复杂度这不就来了，你能够总结下，对于输出数据量 n 的函数，是吧。
搞清楚为什么，怎么定义
那咋去度量“更少的工夫和更少的存储”，复杂度剖析由此而生。
打个不失当的比如
如果把数据结构与算法看做文治招式，那复杂度剖析就是对应的心法。
如果只是学会了数据结构与算法的用法，不学复杂度剖析，这就和你费尽含辛茹苦在隔壁老王家次卧进门右手地砖下偷挖出老王问难村里无敌手的村林至宝王霸拳，然鹅发现秘籍上只有招式，你却没学会暗藏的心法口诀，好好得王霸拳变的王八拳。只有学会了王霸之气，能力虎躯一震，王霸之气一瞨，震走村口光棍李养的哈巴狗。
铁汁：哇，厉害厉害厉害，你胖你说都对，但还是没必要学啊。
小希：???
铁汁：当初很多网站啊包啊，代码轻易跑一下，就能轻轻松松晓得多少工夫占了多少内存啊，算法的效率不就轻松比照进去了么？
小希：。。。。
two 羊吐森破，吃葡萄不吐葡萄皮！
你们说的这种支流叫做 预先分析法。
简略来说，就是你须要 提前写好算法代码和偏好测试数据，而后在计算机上跑，通过最初得出的运行工夫判断算法时效的高下程度，这里的运行工夫就是咱们日常的工夫。
我且不必“万一你吃力心理写好的算法代码自身是个很蹩脚的写法”这种理由反驳你，预先统计法自身存在缺点，它并不是一个对咱们来说有用的度量指标：
首先，预先统计法太依赖计算机的软件和硬件等性能。代码在 core i7 处理器 的就比 core i5 处理器的运算速度快，更不用说不同的操作系统，不同的编程语言等软件方面，就算在同一台电脑上，后面的条件都满足，过后的内存或者 CPU 的使用率也会造成运行时的差别。
举个例子，考查对全国人口普查数据的排序 $n=10^9$，应用冒泡排序 $(10^9)^2$
对于一般电脑 (1GHz $10^9$ flops) 来说，大概须要 $10^9$ 秒(30 年)。
对于天河 1 号超级计算机(千万亿次 = 1P，$ 10^15$ flops)，大概须要 $10^3$ 秒(20 分钟)。
再者，预先统计法太依赖测试数据集的规模。同样是排序算法，你轻易整 5 个 10 个数排序，就算最垃圾的排序，也看起来很快跟火箭一样，不好意思，那 10w 个 100w 个，那这些算法的差距就很大了，而且同样是 10w 个 100w 个数，程序和乱序的所破费工夫也不等。
那问题来了，到底测试数据集选多少才适合？数据的程序如何订好多才行？
说不出来了叭？
能够看出，咱们须要一个不依赖性能和规模等外力影响就能够估算算法效率，判断算法优劣的度量指标，而复杂度剖析天生就是干这个的，为了能本人剖析，所以你必须了解要把握
工夫复杂度
算法的运行工夫
对于某一问题的不同解决算法。运行工夫越短算法效率越高，相同，运行工夫越长，算法效率越低。
那么如何预计算法复杂度？
所有人撤退，咱们很相熟的大 O 闪亮退场！
大佬们甩掉脑阔上最初一根秀发的才发现，当用运行工夫去形容一个算法快慢的时候，算法中执行的总步数显得尤为重要。
因为这只是估算，咱们假如每一行代码的运行工夫都为 Btime(一个比特工夫), 那么算法的总的运行工夫 = 运行的总代码行数。
上面咱们看一段简略的代码。
代码 1
//python
def longgege_sum (m);
sum = 0;
for longgege in range(m);
sum += longgege
return sum;
在下面假如的状况下，这段求累加和的代码总的运行工夫是多少呢？
第二行代码须要 1 Btime 的运行工夫，第 4 行和第 5 行别离运行了 m 次，所以每个须要 mBtime 的运行工夫，所以总的运行工夫就是(1 + 2m)Btime。
若咱们 用 S 函数来示意赋值语句的总运行工夫，所以下面的工夫可表白成 S(m)=(1 + 2m)*Btime, 说人话就是 ” 数据集大小”为 m, 总的步数为 (1+2m) 的算法执行工夫为 S(m)”。
下面的公式得出，S(m) 和总步数是成正比关系，这个法则很重要的，通知了一个易懂的趋势，数据规模和运行工夫之间有趋势!
可能你对数据规模还是没有概念
类比下
对于咱们当初的家用计算机，如果想在 1s 之内解决问题：
O($n^2$) 的算法能够解决大概 $10^4$ 级别的数据
O(n) 的算法能够解决大概 $10^8$ 级别的数据
O(nlogn) 的算法能够解决大概 $10^7$ 级别的数据
大 O 表示法
什么是大 O
很多铁子说工夫复杂度的时候你都晓得 O(n), O($n^2$), 然而说不清什么是大 O
算法导论给出的解释：大 O 用来示意上界的，上界意思说对任意数据输出的算法最坏状况或叫最长运行工夫。
拿插入排序来讲，它的工夫复杂度咱们都说是 O(n^2), 如果数据原本有序的状况下工夫复杂度是 O(n), 也就对于所有输出状况来说，最坏是 O(n^2) 的工夫复杂度，所以称插入排序的工夫复杂度为 O(n^2)。
就是想通知你，同一个算法的工夫复杂度不是变化无穷的，和输出的数据模式仍然有关系，数据用例不一样，工夫复杂度也是不同的，这个要铭刻住。还有平时面试官和咱们探讨一个算法的实现以及性能，指的通常是实践状况下的工夫复杂度。
铁子：我读书少，你可别骗我，你这还是有些形象啊，而且你这实用所有的算法吗，未必吧
小希：你很有精力，你晓得前 n 项和怎么算不，
铁子：这个咱们初中老师讲过的，等差能够算
小希：你就看好上面，这段码
举栗子
// 计算 1 +2+3+....+ n 的和
int sum=0
for(int i=1; i<=n; i++){sum+=i}
能够看到循环了 n 次吧，所以工夫复杂度就是 O(n), 即工夫复杂度就是本程序计算的次数。
如果咱们本人批改后的运行次数函数中，咱们只去保留最高阶项
如果最高阶存在且不是 1，则去除与这个项相乘的常数，是如下表达式：
2n^2+3n+1 ->n^2
所以工夫复杂度为 $n^2$
你可能疑难，为啥会去掉这些值，请看下图
当计算量随着次数原来越大的时候，n 和 1 的区别不是太大，而 $n^2$ 曲线 变得越来越大，所以这也是 2$n^2$+3n+1 -> $n^2$ 最初会估计成 $n^2$ 的起因, 因为 3n+1 随着计算次数变大，根本能够忽略不计。
铁子：就这，你来个略微简单点的吧
安顿
// 利用 sums 办法求三局部和
//java
public static int sums(int n) {
int num1 = 0;
for(int longege1 = 1; longege1 <= n; longege1++){num1=num1+longege1;}
int num2 = 0;
for(int longege2 = 1; longege2 <= n; longege2++){for(int i = 0; i <= n; i++) {num2=num2+longege2;}
}
int num3 = 0;
for(int longege3 = 1; longege3 <= n; longege3++){for(int i = 0; i <= n; i++) {for(int j = 0; j <= n; j++) {num3=num3+longege3;}
}
}
return num1 + num2 +num3;
}
下面这段是求三局部的和，通过之前的学习应该很容易晓得，第一局部的工夫复杂度是 O(n), 第二局部的工夫复杂度是 O($n^2$), 第三局部是 O($n^3$)。
失常来讲，这段代码的 S(n)=O(n)+O($n^2$)+O($n^3$), 依照咱们按“主导”局部，显然后面两个兄弟都间接帕斯掉，最终 S(n)=O($n^2$)。
通过这几个例子，聪慧的铁子们坑定会发现，对于 工夫复杂度剖析来说，只有找出“主导”作用的局部代码即可，这个主导就是最高的那个复杂度，也就是执行次数最多的那局部 n 的量级。
剩下的就是多加练习，无意识的多去练多去想，就能够和我一样 帅气 稳啦。
好吧
我来介绍几种爹，不是，几种阶~
常数阶 O(1)
function test($n){
echo $n;
echo $n;
echo $n;
}
没有循环的，不论 $n 是多少，它只运行 3 次，那么工夫复杂度就是 O(3), 取为 O(1)
线性阶 O(n)
for($i=1;$i<=$n;$i++){$sum+=$i}
相熟的平 (立) 方阶：o($n^2$)/o($n^3$)
$sum=0;
for($i=1;$i<=$n;$i++){for($j=1;$j<$n;$j++){$sum+=$j}
}
两次循环，外面循环执行了 n 次，外层循环也执行了 n 次，所以工夫复杂度为 O(n^2), 立方阶一样
非凡平方阶：O($n^2$/2+n/2)->O($n^2$)
for(){for(){..... ----------->n^2}
}
+
for(){------------> n}
+
echo $a+$b --------------> 1
所以整体上计算次数为 n^2+n+1, 咱们算工夫复杂度为 O(n^2)
对数阶：O(log2n)
int longege = 1
while(longege < m) {longege = longege * 2;}
还是依据之前讲的，咱们先找“主导”，在外面主导就是最初一行，只有算出它的工夫复杂度，这段的工夫复杂度就晓得了。
这段说人话就是，乘多少个 2 就会 >= m?
假如须要 y 个，那么相当于求：
<center>$2^y=m$</center>
即
<center>y=log2m</center>
所以上述代码的工夫复杂度应该为 O(log2m)。
然而这种对数复杂度来说，不论你是以 2, 3 为底，还是以 20 为底，统统记作(logn)
这就要从对数的换底公式说起。
除了数据集规模会影响算法的运行工夫外，“数据的具体情况”也会影响运行工夫。
咱们来看这么一段代码：
public static int find_word(int[] arr, String word) {
int flag = -1;
for(int i = 0; i <= arr.length; i++) {if(arr[i] == word) {flag = i;}
break;
}
return flag;
}
下面这段简略代码是要求字符变量 word 在数组 arr 中呈现的地位，我用这段来解释“数据的具体情况”是什么意思。
变量 word 可能呈现在数组 arr 的任意地位，假如 a=[‘a’, ‘b’, ‘c’, ‘d’]:
- 当 word = ‘a’, 正好是列表中的第 1 个，前面的不须要在遍历，那么本状况下的工夫复杂度是 O(1)。
- 当 word = ‘d’ 或者 word=’e’, 这两种状况是整个列表全副遍历完，那么这些状况下的工夫复杂度是 O(n)。
依据不同状况，咱们有了最好状况工夫复杂度，最坏状况工夫复杂度和均匀状况工夫复杂度这三个概念。
上面看一段代码，咱们别离从最好和最坏的状况上来剖析其工夫复杂度。
// n 示意数组 array 的长度
int find (int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (int i=0; i < n; i++) {if (array[i] == x) {pos = i;}
}
return pos;
}
这段代码的性能是，在一个无序的数组中，查找变量 x 呈现的地位。如果没有找到就返回 -1。抽象的剖析一下：外围代码执行了 n 次，所以其工夫复杂度是 O(n)，其中，n 代表数组的长度。
代码简略优化一下：能够在中途找到符合条件的元素时，提前结束循环。
// n 示意数组 array 的长度
int find (int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; i++) {if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
优化完之后的代码就不能简略粗犷的说其工夫复杂度就是 O(n)了。因为，遍历可能在数组下标为 0 ~ n-1 中的任何一个下标所指向的元素中完结循环，是不是很神奇
持续往下剖析：
- 假如，数组中第一个元素正好是要查找的变量 x，不言而喻那工夫复杂度就是 O(1)。
- 假如，数组中不存在变量 x，那咱们就须要把整个数组遍历一遍，工夫复杂度就成了 O(n)。
所以，在不同的状况下，这段代码的工夫复杂度是不同的。
等我踹口气
嗯~
还有个问题
这几个概念从我置信你从字面意思也能了解，最好工夫复杂度就是，在最现实的状况下，执行这段代码的工夫复杂度。对应假如 1。工夫复杂度就是 O(1)。
同理，最坏工夫复杂度就是，在最蹩脚的状况下，执行这段代码的工夫复杂度。对应假如 2。工夫复杂度就是 O(n)。
均匀工夫复杂度
首先先来说它，又叫“加权均匀工夫复杂度”，为什么叫加权呢？是不是很奇怪，因为，通常计算均匀工夫复杂度，须要把概率思考进去，也就是，咱们计算均匀工夫复杂度的时候，须要一个“加权值”，来真正的计算均匀工夫复杂度。
咱们代码整个例子，对均匀工夫复杂度进行剖析：
// n 示意数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {if (array[i] == x) {
pos = I;
break;
}
}
return pos;
}
代码很简略，示意在一个数组中，要找到 x 这个数，最好复杂度是 O(1), 最坏是 O(n)。
那均匀复杂度是怎么计算呢？
先说简略的平均值计算公式：
下面的代码，所有查找 x 的工夫相加：1 + 2 + 3 +······ + n + n (这个 n 示意当 x 不存在时遍历 array 须要的次数)，另外，须要查找的次数为 n + 1 次，那么后果就是：
代入大 O 表达式，后果是 O(n)。
这个公式表白的是：计算所有可能呈现的状况之和，而后除以可能呈现的状况的次数。说白了，这是一个相对均匀的后果。示意每个后果都可能呈现 n + 1 次。
这是一个较为粗犷的假如。
如果略微应用一个简略的概率来计算呢？
这里有 2 个概率：
x 变量是否在数组中的概率，有 2 种状况—— 在与不在，所以，他的概率是 1/2.
x 变量呈现在数组的概率，有 n 种状况，但只会呈现一次，所以是 1/n.
咱们把两个概率进行相乘，后果是 1/(2n). 这个数，就是“加权值”。
如何应用加权值对下面代码的“复杂度”进行计算？
而后，咱们在这公式上把 (n + 1)换成“权重”：也就是 1/2n。
后果为 3n + 1 / 4。这个也就是“加权后的均匀工夫复杂度”，示意，执行了 1 + 2 + ···· + n + n 次的“加权平均值”。
如果应用大 O 表示法，去除系数，常数，低阶，那么他的最终后果就是 O(n)。
能够看到，前者应用的是分母没有做任何权重的措施，仅仅是简略的 n + 1，而后者，咱们做了简略的权重计算，认为呈现的概率不是 n + 1，而是 1/2n。
能够说，加权值，是为了在前者的根底上，，目标是更加的精确。也就是说，要计算精确的均匀工夫复杂度，就须要精确的计算这个“权重值”，而权重值会受到数据范畴，数据品种影响。因而须要在实际操作中，进行调参。
简略来说，就拿“x 变量是否在数组中的概率”这个值来说，不肯定是 1/2，如果有这样一组数据{y, s, f, f, g, x, g, h}，那么，他的概率还是 1/ 2 吗，实际上只有 1/8，所以，还是得依据理论状况来。
均摊工夫复杂度
啊这，听起来和均匀工夫复杂度有点相熟呢。然而均摊工夫复杂度的利用场景比均匀工夫复杂度更加非凡、更加无限。上面看一段代码：
//array 示意一个长度为 n 的数组
// 代码中的 array.length 就等于 n
static int[] array = new int[]{1, 2, 3, 4, 5};
static int count = 2;
public static void insert(int val) {
// 数组没有闲暇空间的状况
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; i++) {sum = sum + array[i];
}
array[0] = sum;
count = 1;
System.out.println("array.length:::" + array.length + "sum:" + sum);
}
// 数组有闲暇空间的状况
array[count] = val;
count++;
System.out.println("count!=array.length:" + array.length + ",,,count::" + count);
for (int i = 0; i < array.length; i++) {System.out.println("array[" + i + "] =" + array[i]);
}
}
下面实现了向一个数组中插入数据的性能。当数组满了之后，也就是代码中的 count == array.length 时，咱们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个地位，而后再将新的数据插入。但如果数组一开始就有闲暇空间，则间接将数组插入数组。
当初剖析一下这段代码的工夫复杂度，最现实的状况下，数组中有闲暇空间，咱们只须要将数据插入到下标为 count 的地位就能够了，所以最好状况工夫复杂度为 O(1)。最坏的状况下，数组中没有闲暇空间了，咱们须要先做一次数组的遍历求和，而后再将数据插入，所以最坏状况工夫复杂度为 O(n)。
接着咱们按下面的办法剖析一下均匀工夫复杂度。假如数组的长度是 n，依据插入数据的地位不同，咱们能够分为 n 种状况，每种状况的工夫复杂度是 O(1)。此外，还有一种：“额定”的状况，就是在数组没有闲暇空间插入一个数据，这个时候的工夫复杂度是 O(n)。而且，这 n + 1 中状况产生的概率是一样的，都是 1/(n + 1)。
其实，这个例子里的均匀复杂度剖析并不需要这么简单，不须要应用概率的常识。咱们先来比照一下这个 insert() 的例子和下面的 find() 的例子，二者的区别如下：
- 区别一：
首先，find() 函数在极其状况下，复杂度才为 O(1)。但 insert() 在大部分状况下，工夫复杂度都为 O(1)。只有个别情况下，复杂度才比拟高哦，为 O(n)。这是两者间的第一个区别。
- 区别二：
对于 insert() 函数来说，O(1)工夫复杂度的插入和 O(n)工夫复杂度的插入，呈现的频率是十分有法则的，而且有肯定的前后时序关系，个别都是一个 O(n) 插入之后，紧跟着 n – 1 个 O(1) 的插入操作，周而复始而已。
所以，针对这样一种非凡场景的复杂度剖析，咱们不须要像之前均匀复杂度分析方法那样，找出所有的输出状况及相应的产生概率，而后再计算加权平均值，这种就没必要。
针对这种非凡的场景，咱们引入一种更加简略的分析方法：摊还分析法，通过摊还剖析失去的工夫复杂度叫做均摊工夫复杂度。
那到底如何应用摊还分析法来剖析算法的均摊工夫复杂度呢？
持续看这个 insert() 的例子。每一次 O(n) 的插入操作，都会跟着 n – 1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n – 1 次耗时少的操作上，均摊下来，这一组间断的操作的均摊工夫复杂度就是 O(1)。这就是均摊剖析的大抵思路，能够吧？
对一个数据结构进行间断操作中，大部分状况下工夫复杂度都很低，只有个别情况下工夫复杂度比拟高，而且这些操作之间存在前后连贯的时序关系，这个时候咱们就能够把这一组操作放在一起来剖析，看是否能将较高工夫复杂度那次操作的耗时，平摊到其余那些工夫复杂度比拟低的操作上。 而且，在可能利用均摊工夫复杂度剖析的场合，个别均摊工夫复杂度就约等于最好状况工夫复杂度。
总之，均摊是均匀工夫复杂度的极限状况
均摊工夫复杂度可能不是很好了解，尤其是与均匀工夫复杂度的区别。然而，咱们能够将其了解为一种非凡的均匀工夫复杂度。最次要的还是应该把握它的分析方法，这种思维而已。
之所以引入这几个复杂度的概念，是因为，咱们在同一段代码，在不同输出的状况下，复杂度量级有可能是不一样的。在引入这几个概念之后，咱们能够更加全面的示意一段代码的执行效率。
平时大家更多的关怀是最好的工夫复杂度，这没错，进步工夫效率吗没错
但
我感觉更关怀最坏状况而不是最好状况，理由如下：
（1）最坏状况它能给出算法执行工夫的上界，这样能够确信，无论给什么输出，算法的执行工夫都不会超过这个上界，这样为比拟和剖析心里有个底。
（2）最坏状况是种乐观预计，然而对于很多问题，均匀状况和最坏状况的工夫复杂度相差不多，比方插入排序这个例子，均匀状况和最坏状况的工夫复杂度都是输出长度 n 的二次函数。
空间复杂度
空间复杂度跟工夫复杂度相比，你须要把握的内容不多。
也是一样，它也是形容的一种趋势，只不过这趋势是代码在运行过程中 长期变量占用的内存空间。
嗯？长期吗
就要从代码在计算机中的执行摆起啦。
代码在计算机中的运行的存储占用，次要 分成 3 局部
- 代码自身所占用的
- 输出数据所占用的
- 长期变量所占的
前两个它本人就是要必须占用空间，与代码的性能就没关系，所以最初掂量代码的空间复杂度，只关怀在运行过程中长期占用的内存空间。
怎么算？
<center>R(n) = O(f(n))</center>
空间复杂度记作 R(n), 示意模式与工夫复杂度 S(n) 统一。
剖析下
上面咱们用一段简略代码来了解下空间复杂度。
//python
def longege_ListSum(n):
let = []
for i in range(n):
let.append(i)
return let
下面这段中显著有两个长期变量 let 和 i
let 是建了一个空列表，这个列表占的内存会随着 for 循环的减少而减少，最大到 n 完结，所有呢，let 的空间复杂度是 O(n), i 是存元素地位的常数阶，和规模 n 曾经没有关系了，所以这段代码的空间复杂度为 O(n)。
咱们再来看下 它
O($n^2$)
//java
public static void longege_ListSum(n) {int[] arr1 = new int[0];
for(int i=0; i<=n; i++) {int arr2 = new int[0];
for(int j=0; j<=n; j++) {arr1.apend(arr2);
}
}
return arr1;
}
还是一样的剖析形式，很显著下面这的代码手动创立了一个二维数组 arr1, 一维 占用 $n^2$, 所以它就是这段代码的空间复杂度啦。
那二分法是多少
int select(int a[], int k, int len)
{
int left = 0;
int right = len - 1;
while (left <= right)
{int mid = left + ((right - left) >> 2);
if (a[mid] == k)
{return 1;}
else if (a[mid] > k)
{right = mid - 1;}
else
{left = mid + 1;}
}
return NULL;
}
代码中的 k、len、a[] 所调配的空间都不随着解决数据量变动，因而它的空间复杂度 S(n) = O(1)
顺便说下
在最坏的状况下循环 x 次后找到, n / ($2^x$)=1; x=log2n; 它的工夫复杂度就是 log2n。
在斐波那契数求空间复杂度的过程中，须要去思考函数栈帧的过程，比方当咱们求第五个斐波那契数的时候，这时候须要先开拓空间寄存第四个数，而后再开拓空间寄存第三个数；当开拓空间到第二个和第一个数的时候，第三个数失去后果并返回到第四个数中，第四个数的值已知后返回到第五个数，过程外面，最大占用空间即为层数减一。
开拓空间的大小最多等于层数 +1，也就是说求第 N 个斐波那契数，空间复杂度即为 O（N）。
递归算法的工夫复杂度
1）一次递归调用, 如果递归函数中，只进行一次递归调用，并且递归深度是 depth, 那么每个递归函数，它的工夫复杂度为 T, 则总体的工夫复杂度为 O(T * depth)。
比如说，二分搜寻法的递归深度是 logn（每次都是对半分）, 则复杂度是 O(Tlogn)
总结个公式就是，递归的工夫复杂度 = 递归总次数 * 每次递归的次数，空间复杂度 = 递归的深度（即树的高度）
2）两次递归调用（关注递归调用次数）
咱们先看上面这个例子
int f(int n) {assert(n >= 0);
if(n == 0)
return 1;
else
return f(n-1) + f(n-1);
}
怎样才能晓得它的递归次数呢，咱们能够画一棵递归树，再把树的节点数进去
能够看到，这是指数级的算法，很慢很慢的！但这在咱们的搜寻畛域是有很大的意义的。
然而咱们的高级排序算法如，归并，快排也是 2 次递归调用，但工夫复杂度只有 O(nlogn)级别，那是因为
1）下面的深度为 n，而高级排序的深度都只有 logn
2）在高级排序算法中咱们在每个节点解决的数据规模是组件放大的。
斐波那契数列的优化
斐波那契数列循环算法：// 工夫复杂度：O(n)
// 空间复杂度：O(1)
long long Fib(long N)
{
long long first = 1;
long long second = 1;
long long ret = 0;
int i = 3;
for (; i <= N; ++i)
{
ret = first + second;
first = second;
second = ret;
}
return second;
}
int main()
{printf("%u\n",Fib(50));
system("pause");
return 0;
}// 斐波那契数列递归算法：// 工夫复杂度: O(2^n)
// 空间复杂度：O（n）long long Fib(long long N)
{return (N < 3) ? 1 : Fib(N - 1) + Fib(N - 2);
}
int main()
{printf("%u\n",Fib(1,1,50));
system("pause");
return 0;
}留神：
斐波那契数列的工夫复杂度为二叉树的个数；
斐波那契数列的工夫复杂度为函数调用栈的次数即二叉树的深度。
// 斐波那契尾递归算法：（优化）// 工夫复杂度：O（n）// 空间复杂度：O(n)
long long Fib(long long first,long long second,int N)
{if (N < 3)
{return 1;}
if (N == 3)
{return first + second;}
return Fib(second,first+second,N-1);
}应用 矩阵乘方的算法 再次优化斐波那契数列算法。
static int Fibonacci(int n)
{if (n <= 1)
return n;
int[,] f = {{ 1, 1}, {1, 0} };
Power(f, n - 1);
return f[0, 0];
}
static void Power(int[,] f, int n)
{if (n <= 1)
return;
int[,] m = {{ 1, 1}, {1, 0} };
Power(f, n / 2);
Multiply(f, f);
if (n % 2 != 0)
Multiply(f, m);
}
static void Multiply(int[,] f, int[,] m)
{int x = f[0, 0] * m[0, 0] + f[0, 1] * m[1, 0];
int y = f[0, 0] * m[0, 1] + f[0, 1] * m[1, 1];
int z = f[1, 0] * m[0, 0] + f[1, 1] * m[1, 0];
int w = f[1, 0] * m[0, 1] + f[1, 1] * m[1, 1];
f[0, 0] = x;
f[0, 1] = y;
f[1, 0] = z;
f[1, 1] = w;
}
优化之后算法复杂度为 O(log2n)。
请背下来
算法刷题过程中，咱们会遇到各种的工夫复杂度，但就算你代码变出花来，简直也逃不出上面几种常见的工夫复杂度。
上表中的工夫复杂度是由上往下顺次减少，所以 O(1) 效率最高，O(n) 和 O($n^2$) 这两个后面曾经说过了，上表最初一个效率低的离谱，当前要是可怜碰到我了在提一下，就不细说。
可能有些敌人还是纳闷，当初计算机硬件性能越来越强了，咱们为啥还这么器重工夫复杂度呢？
问的很好，咱们能够用几个栗子来比照下，看下之间它们有多大的差距。
有 100 集体站在你背后，你一眼就发现了你喜爱的她。
如果换成 10000 个，后果并没有什么区别。
这就是 O(1) 有 100 集体站在你背后，你得一个一个看过来，能力找到你的女神。无论你用什么程序看，我总有一种方法，把你的女神放在你最初看到的那个。如果换成 10 000 个，你就有了 100 倍的工作量。
这就是 O(n)
如果当初有 100 集体站在你背后，脸盲的你得两两结对、一对一对察看，能力找到惟一的一对双胞胎。同上，我总是能够把双胞胎放在你最初找到的一对。你至少一共要察看 4950 对。
如果换成 10000 个，那就是 49 995 000 对，也就是 10100 倍的工作量
这就是 O(n²)
有 128 集体站在你背后，你要把他们依照高矮排序——咱们假如用归并来解——你先把他们分成两个 64 人的大队，每个大队分成两个 32 人的中队，每个中队分成……直到最初每一个“小小…小队”只剩一个人。显然，一个人肯定是曾经排好序的。
而后反向操作，将刚刚拆分的队伍合并起来。合并队伍的时候，因为曾经排好序，只须要取出两队排头进行比拟，就找到了最矮的一个，取出来——如此进行上来，合成的两倍大的队伍也将是有序的。显然，这个合并操作，是 O(n)的。总共的比拟次数，不会超过两个队伍的总人数。
最初的问题只是，有多少次“宰割 - 合并”操作。每次宰割数量都减半，很显著是 7 次。由此看来，大抵须要执行 7×128 次操作。
这就是 O(nlogn)
不同的工夫复杂度，差距是显著的，好了，上面给出你须要铭记在心里的
数据结构的工夫复杂度
排序算法的工夫复杂度
算法稳定性什么意思？如果排序前两个相等的数据其在序列中的先后地位程序与排序后它们两个先后地位程序雷同，咱们说算法具备稳定性，有什么意义呢？如果排序的算法是稳固的，第一个次排序的后果和关键字段能够为第二个次排序所用。
最初，算法和性能的关系，掂量一个算法的好坏，次要通过数据量大小来评估工夫和空间，这些最初都间接会影响到程序性能，个别空间利用率小的，所需工夫绝对较长。所以性能优化策略外面常常听到 空间换工夫，工夫换空间这样说法。
到这里，复杂度剖析就全副讲完啦，只有你认真看完这篇文章，置信你会对复杂度剖析有个根本的意识。复杂度剖析自身不难，记得平时写代码的时候遇到问题无意识多预计一下本人的代码，感觉就会就会越来越相熟的。
点击关注，第一工夫理解华为云陈腐技术~
