03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？

我不认为是多此一举，渐进时间，空间复杂度分析为我们提供了一个很好的理论分析的方向，并且它是宿主平台无关的，能够让我们对我们的程序或算法有一个大致的认识，让我们知道，比如在最坏的情况下程序的执行效率如何，同时也为我们交流提供了一个不错的桥梁，我们可以说，算法1的时间复杂度是O(n)，算法2的时间复杂度是O(logN)，这样我们立刻就对不同的算法有了一个“效率”上的感性认识。 当然，渐进式时间，空间复杂度分析只是一个理论模型，只能提供给粗略的估计分析，我们不能直接断定就觉得O(logN)的算法一定优于O(n), 针对不同的宿主环境，不同的数据集，不同的数据量的大小，在实际应用上面可能真正的性能会不同，个人觉得，针对不同的实际情况，进而进行一定的性能基准测试是很有必要的，比如在统一一批手机上(同样的硬件，系统等等)进行横向基准测试，进而选择适合特定应用场景下的最有算法。 综上所述，渐进式时间，空间复杂度分析与性能基准测试并不冲突，而是相辅相成的，但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时间复杂度程序，所以在实际编程中，时刻关心理论时间，空间度模型是有助于产出效率高的程序的，同时，因为渐进式时间，空间复杂度分析只是提供一个粗略的分析模型，因此也不会浪费太多时间，重点在于在编程时，要具有这种复杂度分析的思维。

总结 一、什么是复杂度分析？ 1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。 2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。 3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。 4.复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。 二、为什么要进行复杂度分析？ 1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。 2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。 三、如何进行复杂度分析？ 1.大O表示法 1）来源 算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。 2）特点 以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。 2.复杂度分析法则 1）单段代码看高频：比如循环。 2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。 3）嵌套代码求乘积：比如递归、多重循环等 4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。 四、常用的复杂度级别？ 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括， O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶） 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括， O(2^n)（指数阶）、O(n!)（阶乘阶） 五、如何掌握好复杂度分析方法？ 复杂度分析关键在于多练，所谓孰能生巧。

老师好，我们上算法课，老师讲到存储一个二进制数，输入规模（空间复杂度）是O(logn) bit。请问如何理解？

看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔~

老师，代码片段把行号也写上吧。

文章里也说了，性能测试这种是受环境所影响的。作为程序员，我们能做的就是尽可能的降低复杂度，才能让代码在不同的环境下以最快的效率执行。至于是不是浪费时间，我觉得其实是个伪命题。首先按刚刚分析过程来看，通过熟悉练习，简单的代码是可以直接看出来复杂度的也就是不费时间；而比较复杂的代码就容易“一不小心”太“复杂”了，这个时候，为了代码质量考虑分析复杂度的时间也并不浪费。再有甚者，我们学习这个分析法，我觉得更多的是要明白这个理念，在写代码的时候就能关注一下这方面的问题，毕竟复杂的代码在写的过程往往是先分析整体逻辑结构的，并且写的过程也需要不断思考，了解这个理念后才能在写的过程中也思考关注这个点。不然，复杂的一段代码一旦写成，日后因为性能问题重构，更费时间。 以上是对课后题的思考，欢迎批评指正☺。 另: 感觉加法法则那个图，maxf(n)+g(n) 换成max(f(n)+g(n))会不会更好些？

回答 thinkings 的问题 i=1; while (i <= n) { i = i * 2 } 假设n= 20，i每次的取值是2 4 8 16 执行4次，时间复杂度是O(log2n) i=1; while (i <= n) { i = i + 2 } 假设 n=20 i每次取值：3，5，7，9，11，13，15，17，19 ，执行9次，时间复杂度是O(n/2),根据老师讲的 公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，所以是O（n）

一直有一个很纠结的问题，烦请解答一下：O具体是哪一个英文字母的缩写？

没有看懂，所以，我们只要知道 x 值是多少，就知道这行代码执行的次数了。通过 2x=n 求解 x 这个问题我们想高中应该就学过了，我就不多说了。 这里的x不就是代码里的n吗，时间复杂度不是O(n)吗？

第二个例子中，第6.7行为什么是2n平方遍而不是n平方遍呢？