时间复杂度和空间复杂度

• 点击表格内对应链接跳转对应内容⬇️⬇️⬇️

一，算法效率

1 算法的复杂度

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

二，时间复杂度

1 时间复杂度定义

• 程序执行的时候用时间来计时，但是程序执行的时间和硬件和程序本身都有关系，但是我们的取的是程序本事执行的次数，执行的次数决定了程序执行时间的长短，和程序执行时间的快慢，所以时间复杂度计算的核心就是程序执行的次数

2 大O表示法核心规则

• 当出现多种情况的话，我们取最坏情况的复杂度，比如说一个排序，如果最开始需要排序的数据原本就是排好的了，那么我们的时间复杂度就是O(1),但是如果数据原本就是乱的，那时间复杂度就是这个排序算法的时间复杂度，可能是O(n),既然有多种情况，可能是O(1),可能是O(n),我们取的是最坏的结果，也就是O(n)

3 常见时间复杂度（从优到差排序）

三，空间复杂度

1 空间复杂度定义

• 衡量算法额外占用内存空间随数据规模 n 增长的趋势。
  包括了算法创建的数组、对象、变量等额外空间（不计算原始输入本身占用的空间，除非要求“原地”算法）。依然使用大O表示法

• 总结：比如一个程序中，有一个数组，有一个for循环，那么这个数组所占的内存并不计入空间复杂度中算法额外占的空间，因为，空间复杂度明确了是算法额外占用的内存空间，也就是这个变量，必须是单独为了运行算法这个逻辑占用的空间，比如for循环中的初始化变量，判断变量，调整变量，这些变量就是为算法运行而服务的变量，也就是算法为了能够运行申请的空间，而刚刚说的数组，并不是为了支撑算法运行逻辑而申请的空间，是正常数据存储的空间，不是算法运行逻辑申请的空间

• 总结：空间是可能重复利用的，也就是说为了算法额外占用的空间，如果被重复利用，那这个空间只算一次，比如int a 申请了一块内存空间，我反复使用int a，我一直用的都是int a这一块空间，所以这一块空间只算一次

2 递归与空间复杂度

• 递归调用会占用调用栈空间，深度每增加一层，就需要分配新的栈帧。
  如递归求阶乘 factorial(n) 递归深度为 n，空间复杂度就是 O(n)，而不是 O(1)。

• 总结：我们创建两个函数一个A函数，一个B函数，两个函数的实现是一样的，我们先调用A函数，再调用B函数，调用A函数的栈帧空间开辟以后，随着A函数调用结束，A函数的栈帧空间被回收，但是这一块空间的数据并没有被清楚，计算机中没有清除这个概念只有空间权限的概念，这块原本属于A的内存空间随着A函数的调用结束使用权限回归到了计算机，接下来B函数的调用，计算机给B开辟的空间就是刚刚回收的A的空间，这块申请过的空间再一次使用，只不过使用权给到了B函数，而调用的两次函数中，都是使用的同一块空间，所以被计入空间复杂度的空间调用，只有一次，因为两次调用用的都是同一块空间

• 点击表格内对应链接跳转对应内容⬇️⬇️⬇️