视频地址:011复杂度06斐波那契数复杂度_哔哩哔哩_bilibili

菲波纳粹数列的一个方法，一个是这个，一个是这个，一个是递归版本，一个是非递归版本，我们来估算一下它们的复杂度啊，首先我们先算一下这个那这个复杂度数同学们你现在自己来算一下它的复杂度是多少？抓住关键这里有个n那其实就是到n它的时间复杂度其实就是到n对不对？嗯那同学们看一下唉不对啊，这是n减一啊。

好，这是n减一啊，对吧？不是执行n次啊，好，那你不是执行n次，那你就n减一嘛，但是我又说了这个常数项是可以忽略的，那不是还是到n吗？对吧？那不是还有大奥恩嘛对吧？好，所以它是大奥恩，好，那这个是多少呢？

那这个同学们一看啊这个应该是大o一吧，为什么？你看这里一句这里一句，而且要么执行这一句，要么执行这一句，那不就是每次执行一句吗？那他按理来说是不是道义啊？你觉得是道义吗？啊那肯定不是道义啊对吧？如果是道义那他肯定是神速了。

但是你明显发现这里我们写个64的话，它已经很慢了，对吧？那说明它肯定不是倒一，那它是什么呢？我们来分析一下啊分析一下，大家思考一下，大家思考一下，其实这个fibe它的核心计算在哪里？在这个加也就意味着只要你执行一次加，我就算你执行了一次，如果你执行了第二次加你就执行了两次，如果你执行了第三次加你就执行了三次。

说白了他它这个fibe最终执行的指令次数就看fibe这个函数掉了多少次，因为你每调用一次fibe这个函数它都要加一次嘛，对不对？所以我们最终其实是看这个函数被调多少次，这个函数被调多少次，那么这个程序指令去执行多少次，我这样说同学们能不能理解来给我点反馈。

因为你每执行一次函数它都做加嘛，对吧？就看这个函数执行多少次，那这个函数究竟执行多少次呢？我们来看一下啊，我们来看一下我这里画了个图，如果我们这个n是5，如果我们传的是5啊，如果我们传的是5，那我传的是5，大家思考一下，如果传的是5，它就要调用fib14，fib13，所以他肯定要调用这个对吧？

然后调用好，那如果我要调用fib4的话，是不是相当于将4传进来？他又要调用fib3，又要调用fib2，对不对？好，那如果我这里是什么呢？Fib3，它是不是相当于要调用fib2fib1，对不对？

好，而且你思考一下，你再思考一个问题，这两个函数是分开调用的，这两个函数是分开调用的，就是当我把五传进去的时候，当我把五传进去的去的时候，四是在这里调，三是在这里调，那他所以4内部调用水跟三内部调用水他们是分开的，那既然是这样子的话，就会发生什么事情呢？

Fib3内部会调用fib2，会调用fib1，对不对？Fab2内部呢又会调用fabefab0，因为当我们 n是2的时候，它会调用fib1、fib0这个意思。

嗯当然如果我们是调用fib1传的是一就直接这里返回了，它就不会调用别的是吧？这个我们刚刚讲过了，或者如果你这里是fib0，如果你传的是0，它也直接返回，不会加别的，不会调用别的对吧？所以这两个到到此为止就结束了，那我们看左边，由于左边跟右边是独立的，所以它内部也要继续调用。

那这个fab4它要调用谁？它要调用这个fab3，它要调用fab2，那这个fab2呢它又调用fab1，fib0，那这个fib3呢它将fib2、fibe对吧？要这个fib2呢它要调用fib again Lean，所以我们如果将5传进去，它一共调用了fab的次数，就是我现在图上面的这个矩形框的次数。

来，同学们能不能理解？这个图能不能看懂？是不是这个矩形框有多少个？这个fib函数就掉了多少次，对吧？好，同学们发现问题了吗？问题在哪？问题在于重复调用的，你看 fibe掉了多少次啊？4次，fab2掉了3次，fab3掉了2次，fab0掉了三次，说白了他重复调用，其实根本没必要重复调用。

你不觉得唉你你这里算过了FBI3的，你是不是可以把你fabi三算的结果直接拿过来这里用啊，你就没必要再去调f三了，对吧？Fab3了，所以他问题就在于重复掉了，很多重复计算，很多重复计算。第二fib2你只要算一次就好了嘛，对吧？还算这么多次对不对？那这一共是多少次呢？一共多少次呢？我们来算一下啊，我们来算一下。

一加二，我们一层一层来算啊，同学们我们一层层来算，一层1+2+4+8，所以最终其实就是1+2+4+8，那1+2+4+8又是什么东西呢？其实就是2的0次方加2的一次方加2的3次方，那这个2的零次方一直加到2的3次方其实是什么呢？其实就是2的4次方减1，也就是二的n减一次方减1，那二的n减一次方，大家思考一下，其实是不是就是0.5×2n0.5×2n那既然常数项可以忽略，所以它其实就是二的n次方，所以它其实就是大o大o二的n次方，大o二的n次方。

所以同学们这个就算出来了，大o二 n次方，一个是on一个是oo什么二的n次方。

那我们来看一下这两个差别有多大？我们来看一下这两个差别有多大？一个是二的n次方，一个是什么呢？一个是n一个是n同学们来看一下啊，n是这一条，n是这一条，你看很低是吧？非常非常低，数据规模很大，它还比较低，但是这个二的n次方呢数据规模还很小的时候，你看它已经涨到什么？35,000了，对吧？

非常非常大，所以这两个差别是特别特别大的，所以这两个算法真的是天差地别，同学们真的是天差地别，那分析完以后呢，那我们就总结一下这个首先这个代码刚刚已经说了，它是二的二的n次方，这个是n这两个其实差别有多大呢？

我们来给个给个数字啊，如果你有一台一GB啊，如如果你有一台应该说一g一g赫兹的一g赫兹主频的这个普通计算机，那像这种它大概来说运算速度就是呃每秒钟运算10的9次方次，如果我们n等于64，就是这个数据规模假设是64的话，那他们计算大概需要耗多少时间呢？

如果是on大概就耗时6.4×10的-8，对是负数，-8秒，也就是0.0对吧？很多0然后64，所以非常非常快，就如果用这台计算机来算的话，好，那如果是什么呢？二的n次方，那大概是多少时间呢？它需要耗584年才能算完，所以同学们一开始的时候，我这个地方传了64的话，我们一直在等等等，可能等到我们这课程结束了，它的结果还没出来。

这个是如果用这台计算机来算的话，大概就是这样，所以同学们应该是能感受到它的差别，对吧？所以有时候算法之间的差距真的是往往比硬件方面的差距还要大，什么意思呢？比如说你拿一台I7处理器的计算机去算这个，然后你拿一台可能I三处理器算算右边这个真的可能右边这个还更快，就是我处理器比较差，但是我算法好，运行的时间还更短，你尽管你的这个处理器非常强，对吧？

但是你算法不行，你可能耗的时间非常非常长更长，所以同学们注意，算法之间的差距真的是比硬件方面的差距还要大，所以同学们你想想，你平时写代码的时候，如果你不注重算法跟注重算法，真的是差别是特别特别大，所以一定要注重起来重视起来啊那我们再看一下算算法的一个优化方向，那我们怎么去优化一个算法很简单，我们首先第一点用尽量少的存储空间对吧？

第二点用尽量少的执行步骤，这个就是优化了一个方向，而且很多时候我们根据情况还可以怎么样呢？空间换时间或者说时间换空间，什么意思呢？比如说我现在这个开发这个程序是运行到这个 PC PC上面对吧？那PC一般来说内存都是比较大的，那有时候我为了追求时间上的这个极致，那就有可能怎么样？牺牲多一点内存空间，然后保证我们的这个程序的执行时间会降低，这个是有可能的，这个以后有机会会讲到啊还有一个时间换空间，对吧？

比如说如果你运行的是那种微型设备，比如说移动端设备，那有时候我们可能要牺牲一点点时间，而减少内存的开销是有这种可能的，这个以后可能也会遇到这个问题，我们以后再讲好吧，这个是一个优化的一个方向。

那我们再看一个多个数据规模的一个情况，多个数据规模的一个情况，比如说像这个这个有两个数据规模，也就意味着我们这里面的时间复杂度其实是有两个家伙决定的。

你你认真看，你看你这个后循环是跟n有关，你这个后循环是跟k有关，那如果是两个数据规模怎么表示呢？很简单，其实就是这样表示到n加k注意这两个都不能忽略，因为这两个都是变量嘛，都是数据规模，所以这两个都得写一起，那这个很简单。

然后复杂度其实还有更多的支持，更多的支持呢我们会后续再讲数据结构，算法的过程中不断的去穿插，比如说什么最好复杂度、最坏复杂度、均摊复杂度，还有什么平均复杂度对吧？呃复杂度震荡这些东西都会在后面讲到，今天我们先简单了解就可以。