算法复杂度

算法是指解决问题的方案准确而完整的描述，是一系列解决问题的清晰指令，算法代表着：用系统的方法解决问题的策略机制。

是解决问题的方法和步骤

如果 a + b + c = 1000,并且 a^2 + b^2=c^2，求出所有的：a\b\c的组合

我们不同的算法解决相同的问题，算法的成本是不同的。总体上来讲，一个优秀的算法追求两个目标：

1. 在程序中，占用最少的内存空间区完成需求
2. 花最少的时间去完成需求

结论：我们的算法研究的如何花最少的时间和占用最少的内存空间去完成相同的需求

算法是一种解决问题的方法。我们需要将：时间占用和空间占用量化。有关算法的时间耗费分析，我们称为算法的时间复杂度分析，算法空间的耗费分析，我们称为空间的复杂度分析

1. 时间维度：是指执行当前算法所消耗的时间，时间越短，算法越好

   这么认为：代码执行次数越多，耗费时间越长，效率就越差。我们需要多写一些短小精悍的代码来提高代码的执行效率

   时间复杂度：看作是一个代码执行的时间趋势。执行次数与执行参数息息相关。如果一个问题的规模是n，解决这个问题的某一算法所需要的时间T(n)

   算法的时间复杂度说的是：一个算法的执行时间根据数据规模增长的一个趋势

   40亿的数据要求搜索，线性查找法：最坏的情况，40亿条数据，40亿次操作

   二分查找：32次操作就可以完成

   算法的时间复杂度：即算法的时间度量

   T(n) = O(f(n)) // 大O表示法
   

   ​ O后面的括号，括号中是一个函数。指明某个算法耗时与数据增长量之间的关系。

   ​ n：代表的是输入数据的量

   ​ T：代表的是算法需要执行的总时间

   ​ 大O表示法：表示代码执行时间随数据规模增长的变化趋势，时间复杂度表示的是变化趋势，并不是真正的执行时间。

   分析算法的时间复杂度时：

   1. 算法完成工作最少需要的基本操作，最优的时间复杂度
   2. 算法完成工作最多需要的基本操作，最坏的时间复杂度
   3. 算法完成工作平均需要的基本操作，平均时间复杂度

   对于最优的时间复杂度，意义不大，因为它没有提供有用的信息，它反映的是最乐观、最理想的情况，没有参考价值

   最坏的时间复杂度，提供了一种保证，表明算法在这个程序的基本操作中一定可以完成需求

   平均时间复杂度，是对算法的一个比较全面的评价，不是每一个计算都能够在这个基本操作中完成

   常见的时间复杂度：

   1. 常数阶：O(1) ，T(n) = O(1)，时间复杂度是常数级别的。表示无论n的规模如何增长，它的执行时间基本是不变的。常数阶是最低的时间复杂度。
   2. 线性阶：O(n) ，T(n) = O(n)，代表数据量增大几倍，耗时也增大几倍。常见的算法：遍历
   3. 平方阶：O(n²)，T(n) = O(n²) ，代表的是数据量增大n倍时，耗时增大n的平方倍。两层循环
   4. 立方阶：O(n³)，T(n) = O(n³) ，代表的是数据量增大n倍时，耗时增大n的立方倍。三层循环
   5. 对数阶：O(logn)，T(n) = O(logn)，当数据增大n倍时，耗时增大logn倍 ，二分查找，n 以倍数的规模递减 n => n / 2 => n/4
   6. 线性对数阶：O(logn)，T(n) = O(nlogN)，就是n乘以logn，当数据增大n倍，耗时会增大n * logn倍
   7. 指数阶：O(2ⁿ)，当数据增大n倍时候。耗时增大2ⁿ倍

   计算时间复杂度

   1. 基本操作，即只有常数项，认为这个时间复杂度就是O(1)
   2. 顺序结构，时间复杂度按加法
   3. 循环结构，时间复杂度按乘法
   4. 分支结构，时间复杂度取最大值。

   判断一个算法的效率的时候，往往只需要取关注操作数量的最高次项。

   优劣对比：O(1) < O(logn) < O(n) < O(logn) < O(n²) < O(n³) < O(2ⁿ)

   越小表示算法的执行时间越短，算法效率越高

2. 空间维度：是指执行当前算法所消耗的内存空间

   S(n) = O(f(n))
   

   空间复杂度是对一个算法在运行国中临时占用存储空间大小的度量。表示的是：算法存储空间与输入值之间的关系

   通常来讲，只要我们的算法不涉及到动态的空间，递归，栈，空间复杂度通常为常数O(1)

   算法的空间复杂度，并不是计算实际占用的空间，而是计算整个算法的辅助空间单元（变量）的个数，与问题的规模没有关系，空间复杂度主要看新开辟的变量个数