大家好，我是讯享网，很高兴认识大家。



 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> 

讯享网

在我们学习数据结构之前，我们肯定就听过某某大神说，我的排序算法的时间复杂度只需要O(logN)，空间复杂度只需要O(1)…听的好唬人，但是实际也真牛。那其中时间复杂度和空间复杂度是什么呢？不才这篇笔记就深入讲解。

---

---

讯享网

我们写了上面递归的方法来计算，代码干净、简洁和明了，那他是一个好算法吗？结果显而易见，差的不行，如果我们计算第30位的斐波拉系数，大约需要进行10亿次计算，这非常恐怖。也仅仅是第30位。

---

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。 在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

---

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

简单的说就是这个程序需要最长循环运行多少次。

• 在第一次N次循环中，又内嵌了一层N次循环，那此时第一次循环从开始到结束要运行（N*N）次。
• 在第二次循环中，他的循环次数是2*N次循环，即要运行2*N次
• 在第三次循环中，M的初始值是：10，每次循环渐渐，即最终会循环10次。

统合上述三次循环，我们就可以的出，运行一次函数需要运行多少次。
Func1 执行的基本操作次数 ：

讯享网
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

---

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则与这个项目相乘的。得到的结果就是大O阶。

使用大O的渐进表示法以后，的时间复杂度为：O(n²)

因为是渐进表示法，保留最高位指数位即可，因为若n为无穷时候，在极值运算中，我们可以认为：

虽然在数学中上面式子依旧是无穷大，不是，但是为了具象表示大O的渐进表示法选择举例上图。这样方便理解。
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

在实际中一般情况关注的是算法的运行情况

---

通过上面列举的推导大O阶方法，来计算一下下面的例子。

栗子1：

讯享网

• 先找出循环次数最多的循环，上例中有两个循环，一个是次循环，一个是次循环
• 那么上例中为：。因为相乘的常熟可以被去除。

栗子2：

• 先找出循环次数最多的循环，上例中有两个循环，一个是次循环，一个是次循环
• 由于两个都是，所以为：O(N+M)。

栗子3：

讯享网

• 先找出循环次数最多的循环，上例中只有一个循环，是一个常数次循环。
• 那么他的时间复杂度就为：O(1)。

栗子4：

• 上面代码是个二分查找。每次运行都会去除一半的结果。
• 最好的结果是O(1)，即我们第常数次就找到了。
• 最坏的结果，是每次折半，直到最后成为一个值的时候才找到。此时我们有个值，每运行一次二分查找都对 /2，
  即最坏的结果： /2 /2 /2…/2 = 1 => = 1*2 *2 *2…*2。现在我们设进行了次二分查找，可以得出： = 2^x。那次就等于：log₂^N。时间复杂度就为：O(log₂^N)。
  
• 在数据结构的和，书写 log₂^N 这样的格式比较困难，也比较麻烦，所以我们统一把 log 以2为底(log₂ )的编写成 ，不同于数学中的 lg 才表示2为底。
• 在上面栗子中，我们取最坏的结果，二分查找的时间复杂度：O(logN)。

栗子5：

讯享网

• 我们可以画出树形图来观察（如下图）
• 可以观察到整体而言，递归的次数等比数列的和，虽然有些会提前结束，但是对整体而言可以忽略不计。根据 等比数列和 公式可以得出 递归次数为:(2^N-2）
• 时间复杂度为：O(2^N)。

---

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了， 因此 空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

栗子1：

• 动态开辟了个个字节空间，此时空间复杂度为O(n)。

栗子2：

讯享网

• 在循环中只是调用了变量，没有在循环内部创建变量，所以空间复杂度为：O(1)。

栗子3：

• 递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

---

---

以上就是本章所有内容。若有勘误请私信不才。万分感激💖💖 如果对大家有帮助的话，就请多多为我点赞收藏吧~~~💖💖

ps:表情包来自网络，侵删🌹