相信每个录音机都接触过时间复杂度。《代码随想》已经讲了上百个经典话题。现在是深入分析时间复杂度的时候了。我很久以前写的。一，当时没有人看文章，Carl觉得有价值的东西应该让更多人看到，哈哈。那么重组后的时间复杂度篇正式和大家见面啦！什么是时间复杂度？“时间复杂度是一个定性描述算法运行时间的函数。”在我们的软件开发中，时间复杂度是用来方便开发者预估程序运行的响应时间。那么如何估算程序的运行时间呢？通常，估计算法的运行单元数来表示程序所消耗的时间。在这里，CPU各单元消耗的时间默认是一样的。假设算法的问题规模为n，运算单元的个数用函数f(n)表示。随着数据规模n的增加，算法执行时间的增长速度与f(n)的增长速度相同，称为算法的渐近时间复杂度，简称时间复杂度，记为O(f(n))。什么是BigO这里的BigO是什么意思？说到时间复杂度，“大家都知道O(n)、O(n^2)，但分不清BigO是什么”。算法导论中给出的解释：“大O用来表示上界”，当它作为算法最坏情况运行时间的上界时，就是对于任何数据输入。同样算法介绍举个例子：以插入排序为例，我们都说插入排序的时间复杂度是O(n^2)。输入数据的形式对程序运行时间影响很大。当数据本来是有序的时候，时间复杂度是O(n)，但是如果数据是倒序的，插入排序的时间复杂度是O(n^2)，即对于所有的输入情况，最坏的时间复杂度为O(n^2)，所以插入排序的时间复杂度称为O(n^2)。同样的，我们再来看一下快速排序。我们都知道快排是O(nlogn)，但是当数据已经有序的时候，快排的时间复杂度是O(n^2)，”所以严格按照大O的定义，快排的时间复杂度应该是O(n^2)”。“但我们还是说快排是O(nlogn)时间复杂度，这是业界默认的规定，这里说的O代表一般情况，并不是严格的上界。”如图：我们主要关注的是一般的数据形式。“面试的时候说算法的时间复杂度是指一般情况。”但是如果面试官跟我们深入讨论一个算法的实现和性能，他一定时刻牢记数据用例不同，时间复杂度也不同。这是必须要注意的。不同数据规模的差异下图可以看出不同算法在不同数据输入规模下的时间复杂度差异。时间复杂度，不同数据规模的差异在决定使用哪种算法时，时间复杂度越低越好（因为简化的时间复杂度忽略了常量项等），要考虑数据规模，如果数据规模是非常大的小甚至O(n^2)算法比O(n)算法更合适（当有常数项时）。就像上图中n为20之前的O(5n^2)和O(100n)，显然O(5n^2)更好，耗时最少。那为什么在计算时间复杂度的时候忽略常数项系数，也就是说O(100n)是O(n)的时间复杂度，O(5n^2)是O(n^2)的时间复杂度2)，默认的O(n)应该比O(n^2)好吗？这又涉及到大O的定义，“因为大O是数据量级突破一个点时的表现，数据量级非常大，这个数据量也是常数项的系数做的数据量起不到决定性作用。”比如上图中的20就是那个点，只要n大于20，常数项的系数就不再具有决定性了。”所以我们在讲时间复杂度的时候，省略了常数项的系数，因为一般来说，默认的数据大小已经足够大了。基于这一事实，给定算法的时间复杂度排序如下“：O(1)常数阶
