时间复杂度

一.算法

算法 Algorithm 是指用来操作数据、解决程序问题的一组方法。

将我们需要操作的数输入，通过算法就可以产出我们目的值作为输出

人们使用算法的目的就在于两个字“效率”

对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

那么我们应该如何去衡量不同算法之间的优劣呢？

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。

空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

二.时间复杂度

想要知道一个算法消耗了多少时间，直接运行一遍可能是最直白的，但不是最准确的，一个算法的时间消耗会受到数据量与硬件性能的很大影响，并且在研发过程中，我们也做不到把完整的算法写出来再次测试时间，这太傻了。

所以我们可以通过一些条件来估算出程序运行的时间消耗，时间复杂度就是用来方便估算出程序运行的答题时间。

那么该如何估计程序运行时间呢，通常会估算算法的操作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示，随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O ( f ( n ) O(f(n)O(f(n))