来来来，让我们重新认识算法的复杂性！

0。前言大家好，我是一个多选参数程序员，一个正在“研究”操作系统（主要是容器），学习数据结构和算法，Java的铁杆新手。今天的文章主要讲一下算法的时间复杂度和空间复杂度。主要参考来源是王政老师的专栏《数据结构与算法之美》和老师去年上课的课件。另外，程序还煮了一个关于算法的github仓库：https://github.com/DawnGuoDev/algorithm。仓库除了基本的数据结构和算法实现之外，还整理了数据结构和算法的知识内容，LeetCode刷题记录（多解，Java实现），部分优质书籍。复杂度分析是整个算法学习的精髓，只要掌握了，数据结构和算法的内容基本上就掌握了一半。》1.动机——为什么需要复杂度分析后统计法（即运行一次代码，通过统计和监控得到运行时间和内存大小）测试结果对测试环境的依赖性很大，影响很大由数据规模大。但实际上，需要一种方法，可以估计算法的执行效率，而不需要具体的测试数据。2.大O复杂度表示法算法的执行效率简单来说就是算法的执行时间算法。例如下面的代码假设每行代码的执行时间相同，都是unit_time。基于这个假设，这段代码的总执行时间是(2n+2)*unit_time.intcal(intn){intsum=0;inti=1;for(;i<=n;++i){sum=sum+i;}returnsum;}通过这个例子可以看出总的执行时间T(n)与每一行代码的执行次数成正比，公式为T(n)=O(f(n))，其中en是数据的大小，f(n)代表每行代码执行的总次数，O()代表一个函数。也就是说，T(n)与f(n)成正比。在本例中，T(n)=O(2n+2)，这种方式称为大O复杂度表示法。但实际上，大O时间复杂度并不具体代表代码执行的真实执行时间，而是代表代码执行时间随数据规模增长的变化趋势，也称为渐近时间复杂度，简称时间复杂度。那么，在公式2n+2中，系数2和常数2不控制增长趋势，比如是线性的，并没有因为系数2或常数2而改变它的线性增长趋势，所以它可以写成T(n)=O(n)。又如T(n)=O(n^2)，表示代码执行时间随数据大小n的增加的变化趋势为n平方。下图展示了不同的时间复杂度，执行时间随着数据规模的增长而变化3.时间复杂度分析如何分析一段代码的时间复杂度？可以采用以下方法只关注循环次数最多的一段代码因为大O复杂度表示法只代表一个趋势，所以公式中的常数项、低阶、系数等可以忽略,并且只能记录最大幅度。因此，在分析一个算法或一段代码的复杂度时，只需关注循环次数最多的那段代码即可。比如下面的代码，时间复杂度为O(n)intcal(intn){intsum=0;inti=1;for(;i<=n;++i){sum=sum+i;}returnsum;}加法规则：总复杂度等于量级最大的代码的复杂度。这主要是为了省略大O复杂度中的低阶项。个人感觉这个方法和上面的方法有些重叠。比如下面这段代码，按照循环可以分为三段。第一段有一个循环，但是循环的次数是常数项，对增长趋势没有影响，所以时间复杂度为O(1)。第二段代码的时间复杂度是O(n)，第三段代码的时间复杂度是O(n^2)。这三段中最大的一段的时间复杂度也就是整个代码的时间复杂度。intcal(intn){intsum_1=0;intp=1;for(;p<100;++p){sum_1=sum_1+p;}intsum_2=0;intq=1;for(;q=0;--i){printouta[i]}}用于空格复杂度分析，其实还是比较简单的。一般取决于变量声明时的分布情况。空间的大小是足够的。4.1.常用的时间复杂度度量阶是指常量阶O(1)，线性阶O(n)平方阶O(n^2)常用的空间复杂度就是以上三种，对比如O(nlogn)和O(logn)数序复杂度一般不用。5.总结回顾一下复杂度分析，一般来说，时间复杂度的动机是我们想在没有具体数据的情况下估计算法执行效率的一种方法。时间复杂度使用BigO表示法，它实际上描述了一个增长趋势。比如在n^2中，当n的值变大时，O(n^2)算法的执行时间呈二次方增长，而O(n)算法的执行时间呈线性增长。所以O(n^2)的时间复杂度更高（见第一张图）。然后是几种常用的时间复杂度，平均时间复杂度，最佳和最坏时间复杂度，摊销时间复杂度（摊销的思想一定程度上体现在操作系统中：在RR调度算法中，在时间slicesize在选择上，也有类似的处理方式，因为RR是抢占式调度算法，当调度发生时，会发生进程的上下文切换，进程的上下文切换需要额外的时间成本，而这个时间成本会平均分配到时间片上，当时间片很大的时候，均衡的效果明显好，所以这个额外的时间成本的影响会很小）为什么说掌握时间复杂度就是基本方法？去年上课的时候印象最深的是，老师好像在讲一道很难的算法题，然后从最简单最复杂的解开始，然后跟着我们分析每一块的时间复杂度一步一步的代码，然后说这段代码的时间复杂度是O(n^2)，能不能想办法降低呢？然后我们就想着怎么降低那里，一句一句看代码，画图等等，最后把时间复杂度降低了。所以我个人感觉掌握了时间复杂度分析之后，掌握的就是算法的分析方法。你可以分析每一段代码的复杂度，然后通过思考最终降低对应代码的时间复杂度。如果你不熟悉复杂度分析，那么你不知道如何降低它，那么算法的优化就没有了。本文转载自微信公众号“多选参数”，可通过以下二维码关注。转载本文请联系多选参数公众号。