在此之前，看了许多的算法文档，以及书记。下面整理了一些基础的算法，加深自己的理解程度，也可以让小伙伴不懂的地方，能够理解，如果能指出不足之处，非常感谢，言归正传！
一、算法最最基础
开始讲之前先刻画算法的运行时间：
image.png
大家想一下这段代码会运行多长时间？
(图1)你预测当n=1000的时候，这个程序运行多长时间，你首先要知道程序运行时间都华仔哪里了，当电脑运行这段代码的时候，执行任何一条语句都需要花费时间，这是时间花费的主要地方。我们现字把每一条语句的执行时间都看作一样的，记为一个时间单元。
(图1)
(图2)这个程序有几个地方消耗了时间：
① 蓝色框的两条语句，花费两个时间单元
②黑色框的一条语句，花费n+1个时间单元
③红色框的两条语句，花费2*n个时间单元
一共花费了3n+3个时间单元，可以看出程序消耗的时间和你的n成线性关系，现字我用T(n)表示这个程序运行多长时间，那么这个程序运行的时间就可以写成：T(N)=3n+3。
图2
我们一般只关心随着问题规模n趋于无穷时函数中对函数结果影响最大的项，也就是最高次项。比如说：T(n)=3n+3,当n非常大的时候常数3和n的系数3对函数结果的影响就很小了(图4)，所以一般我们会保留最高次项并忽略该项的系数，比如： T(n)=n+1 忽略常数项 T(n)~n
T(n)=n+n^2 忽略低阶项 T(n)~n^2
T(n)=3n 忽略最高阶的系数 T(n)~n
图4
所谓低阶项，简单地说就是当n非常大时，这个项相对于另外一个项很小，可以忽略，比如n相对于n^2,n就是低阶项。具体要用数学知识，我们只需记住(图5)的大小关系就行了，到时按照这个进行忽略（相对较小的忽略）。化简完后的函数可以近似地代表原来函数的总体趋势，简化后的式子被称为这个程序算法的时间复杂度，记做O(f(n)),f(n)就是简化后的式子，比如说刚开始讨论的T(n)=3n+3,简化后T(n)~f(n)=n,那我们记为O(n)
图5
常见算法的时间复杂度以及空间复杂度如(图6):
图6
一. 时间复杂度（Time complexity）
时间算法度是学习算法的基石，请大家带着两个疑问看下去.常见的时间的时间复杂度有一下几种：
| 序号 | 描述 | 时间复杂度 |
|---|---|---|
| 1 | 常数阶 | O(1) |
| 2 | 对数阶 | O(logn) |
| 3 | 线性阶 | O(n) |
| 4 | 线性对数阶 | O(nlogn) |
| 5 | 平方阶 | O(n²) |
| 6 | 立方阶 | O(n³) |
| 7 | n次方阶 | O(mⁿ) |
| 8 | 指数阶 | O(2ⁿ) |
| 9 | 阶乘阶 | O(n!) |
1. 什么是时间复杂度？
时间负责都是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串长度函数。时间复杂度通常用大O符号表述，不包含这个函数的低阶项和首项系数（简单总结：是程序运行的时间，也可以说成次数）。
2. 怎么计算时间复杂度？
前面可以总结出计算算法复杂度大O的方法。
第一步：得出运行时间的函数。
第二步：对函数进行简化。
①用常数1来取代运行时间中所有加法常数
②修改后的函数中，只保留最高阶项
③如果最高阶项存在且不是1，则忽略这个项的系数
举个例子：
image
(图7)显然，T(n)=3,对这个函数进行简化，用常数1取代常数3，然后取代后的函数没有最高阶项，那么这个算法的时间复杂度就是O(1)。一般来说，最内层执行次数最多的语句就决定了整个算法的趋势（图8）。
image
你只要看看最内层的语句执行次数的规律就行了，这个内层打印语句随着问题规模n的增加会呈线性增加，直接就可以判定复杂度为O(n) 。按照这个方法就很容易得出下面(图9)这个嵌套的两层for循环的复杂度为O（n^2）了 。最内层的语句随n的增加会呈二次函数的规律执行，代表了这个算法执行时间的一个趋势，（图10）它随着自变量的增大，因变量增长的很慢，对数函数的趋势显然比线性函数好(对数函数随着自变量的增大因变量增长的很慢)
image
image
请看下面这张图(图11)，你可以算出它的复杂度吗？
图11
这段代码的复杂度就为对数级别的，O(logn),其实和之前分析方法一样，我们着重看执行次数最多的内层代码语句(图12)，每循环一次，sum就给自身乘以2，乘了多少次就跳出循环了呢(大于等于n)？不知道，就设为x吧，那么2^x=n,解出x=logn，这说明随着n的增大，最消耗时间的内层语句是呈对数变化的，复杂度的内容很多，你只要理解它的含义以及会分析简单的算法就行了，以后遇到复杂的。
图12
二. 空间复杂度（Space Complexity）
一个程序的空间复杂度是指运行完一个程序所需内存的大小，利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。
(1) 固定部分：这部分空间的大小与输入/输出的数据的个数多少、数值无关，主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，这部分属于静态空间。
(2) 可变空间：这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等，这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。
1、空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
2、一个算法在计算机上占用的内存包括：程序代码所占用的空间、输入输出数据所占用的空间、辅助变量所占用的空间这三个方面。程序代码所占用的空间取决于算法本身的长短，输入输出数据所占用的空间取决于要解决的问题，是通过参数表调用函数传递而来，只有辅助变量是算法运行过程中临时占用的存储空间，与空间复杂度相关。
3、通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为0(1)。
4、算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数，与问题的规模没有关系。
三. 时间复杂度与空间复杂度的联系
- 对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间;反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。
- 另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法（特别是大型算法）时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。
- 有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3。（1）当输入量n＜20时，有T1(n)＞T2(n)，后者花费的时间较少。（2）随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
参考:
https://www.jianshu.com/p/a64a1114f3a9
https://mp.weixin.qq.com/s/070nYGokM96aorZn6MZTDA
