总结
一、什么是复杂度分析？
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!)（阶乘阶）
五、如何掌握好复杂度分析方法？
复杂度分析关键在于多练，所谓孰能生巧。

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

以上是对课后题的思考，欢迎批评指正☺。
另: 感觉加法法则那个图，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）

本节通读两遍，通俗易懂，对复杂度的概念有了新的认识。
复杂度就是用来分析算法执行效率与数据规模之间增长关系。
思考题，性能测试与复杂度分析不冲突，原因如下：
1、性能测试是依附于具体的环境，如SIT、UAT机器配置及实例数量不一致结果也有差别。
2、复杂度分析是独立于环境的，可以大致估算出程序所执行的效率。
3、将复杂度熟记于心，能够写出更高效率、更好性能的代码。若某接口通过性能测试，达不到预期，还可以用复杂度分析接口代码，找出最影响性能的代码，进行优化。

每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？
这个问题分两种情况讨论
1、开发过程中，码代码的过程中就能得出其复杂度，这并不会太多的浪费时间，同时只有分析了每段代码的复杂度，才能估算出它们的执行效率。
2、优化代码时，只有在分析每段代码的复杂度后，才能定位问题代码，才能做相应优化

另外提出两个问题：
1、评论太多，也无法进行关键字搜索，一般没有时间爬楼全部看完，导致不同学友提出一样的问题
2、评论太多，可能有些评论不正确，需要官方确认正确与否，以免误导学友。

03
大家好，这是我的总结：

公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略
1. 只关注循环执行次数最多的一段代码
2.加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积


只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们集作O(1)
不同数据规模，无法评估 m 和 n 的量级大，所以不能利用加法法则，去掉某一个，而是 O(m+n)

空间复杂度：表示算法的存储空间与数据规模之间的增加关系

额外说一下：log3n 就等于 log32 * log2n 其实是利用换底公示推导，有疑问的搜一下。

很有必要，现在是大数据时代，如果是矩阵计算，那就是on，如果是传统双for遍历那就是on²，做lr不依托矩阵都要天荒地老，那神经网络尤其是rnn就不用做了，即使是84万文本数据，长度为20个词，用单机gpu加速要跑七天。双for是几天那？经典例子是马踏棋盘，没优化代码跑几天，优化了又看不懂，问问老师如何对代码做优化，因为优化了就读不懂了有没有？
空间复杂度也有必要，还是nlp的例子，如果是embending的话，内存开销和磁盘开销都小的多，虽然现在分布式允许无限大，但是生产环境要把数据传到hdfs，再传到训练集群上，这都有网络传输开销啊，其二是可能没有这个权限，不安全。其三，生成npy文件不能shuffle，很不便利，也不允许分割，所以事先要想好空间要怎么来。当然时间更重要，敏捷迭代。