重拾算法与数据结构之时空复杂度
时间复杂度和空间复杂度是学习数据结构的关键
1.大O复杂度表示法
举个例子：
T(n) = unit_Time*(n^2+2n+1)
T(n)：代码运行的总时间
unit_Time:每行代码运行的时间
n^2+2n+1:表示代码执行的行数
n:一行代码的执行次数
按照上面的例子推出大O表达式：
T(n)=O(f(n))：n表示数据规模；f（n）表示代码执行的次数；O表示代码的执行次数与代码的执行时间成正比
所以上面例子可以表示为 O（n^2+2n+1）
大O时间复杂度并不表示代码的执行时间，而是表示代码的执行时间随数据规模的增长趋势，也叫渐近时间复杂度，简称时间复杂度。
当数据规模n很大时，公式中的低阶，常量和系数都不能左右增长趋势，所以可以忽略，只需要记录最大量级，所以如果用大O表示法表示上面的例子 ：O（n^2）。
2.时间复杂度分析
1）只关注循环字数最多的一段代码
2）加法原则，这段代码多处循环，总复杂度等于量级最大的代码复杂度
3）乘法原则，嵌套代码的复杂度等于嵌套内外的代码复杂度的乘积。
3.几种常见的时间复杂度分析
对于复杂度量级，可以区分为两类：多项式量级和非多项式量级（O（2^n）,O（n！））
对于非多项式量级的问题我们称为NP问题，当数据规模n增加时，非多项式量级的执行时间会急剧上涨，所以非多项式量级的算法是很低效的。
主要介绍下多项式量级的复杂度
1）O（1）：并不表示只执行一行代码，而是常量级。并不随n发生变化。
2）O（logn），O（nlogn）：
如下代码：
i = 1；
while（i <= n）{
i = i*3
}
这段代码的执行次数是log3n 时间复杂度是O（logn）
不管对数的底是多少，我们都可以使用logn表示时间复杂度。这是因为对数间可以相互转换。log3n*log23 = log2n。
3）O（m+n）,O（m*n）
代码的复杂度由两个数据规模决定，不能确定m，n谁更大
4.空间复杂度
空间复杂度就是渐近空间复杂度，表示算法的存储空间与数据规模之间增长关系。
int[] a = new int[n];
空间复杂度为O（n）；