1.数据结构与算法之美（入门篇）

一、为什么要学习数据结构和算法
1.建立时间复杂度、空间复杂度意识、写出高质量的代码，能够设计基础架构、提升编程能力、训练逻辑思维
2为什么学习数据结构和算法？我认为有3点比较重要
a直接好处是能够有写出性能更优的代码。
b算法，是一种解决问题的思路和方法，有机会应用到生活和事业的其他方面。
c长期来看，大脑思考能力是个人最重要的核心竞争力，而算法是为数不多的能够有效训练大脑思考能力的途径之一
二、

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符字符串匹配算法。
三、为什么需要复杂度分析？
事后统计法：通过把代码跑一遍，通过统计、监控得到的算法执行的时间和占用的内存大小。
**但是事后统计法

1.测试结果非常依赖测试环境
测试环境中的硬件不同会对测试结果有很大的影响。如不同的处理器；不同的机器
2.测试结果受数据规模的影响很大
对于同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别。
如：数据已经有序，那么排序算法不需要做任何操作，执行时间就会非常短；如果数据规模非常小，测试结果可能无法真实的反应算法的性能。（对于小规模的数据排序，插入排序可能反倒会比快速排序要快）
3.大O复杂度表示法
例1：
int cal(int n) {
int sum = 0; //执行1遍
int i = 1; //执行1遍
for (; i <= n; ++i) { //执行n遍
sum = sum + i; //执行n遍
}
return sum;
}
如果每个执行代码需要时间 unit_time，执行次数为 (2n+2)
那么执行时间为 (2n+2)unit_time
例2：
int cal(int n){
int sum=0; //执行1遍
int i=1; //执行1遍
int j=1; //执行1遍
for(;i<=n;++i){ //执行n遍
j=1; //执行n遍
for(;j<=n;++j){ //执行n^2遍
sum=sum+ij; //执行n^2遍
}
}
}
如果每个执行代码需要的时间为unit_time,执行次数为(3+2n+2n^2)
那么执行的时间为（3+2n+2n^2)*unit_time
----虽然我们不知道unit_time的具体的值，但是我们可以得到一个重要的规建:
所有的代码执行时间T(n)与每行代码的执行次数n成正比
总结公式为：
T（n)=O(f(n))
//n表示数据规模的大小;f(n)表示每行代码执行的次数总和;
公式中的O,表示代码执行时间T(n)与f(n)表达式成正比
所以例1中T(n)=O(2n+2)
例2中T(n)=O(3+2n+2n^2)
这就是大O时间复杂度表示法.(大O时间表示法实际上并不是具体代表代码真正的执行时间,而是表示代码执行时间随数据规模的增长变化趋势,所以也叫渐进时间复杂度)
4.时间复杂度分析
如何具体分析一段代码的时间复杂度
a.只关注循环执行次数最多的一段代码
b.加法法则:总复杂度等于量级最大的那段代码的复杂度
例:
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p; //执行了100遍
}

int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q; //执行了n遍
}

int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
} //执行了n^2遍
}

return sum_1 + sum_2 + sum_3;
}

强调:即使有一段代码循环了10000次、100000次，只要是一和已知的数，跟n无关，照样也是常量级的执行时间。当n无限大的时候，就可以忽略。尽管对代码的执行时间会有很大影响，但是回到时间复杂度的概念来说，他表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量执行时间多大，我们都可以忽略掉。因为他本身与增长的趋势并没有影响。
第二段代码时间复杂度：T(n)=O(n)
第三段代码时间复杂度: T(n)=O(n^2)
综合这三段代码的时间复杂度，我们取其中最大的量级。所以整段代码的时间复杂度就为O(n^2)
也就是说总的时间复杂度就等于量级最大的那段代码的时间复杂度。
T2(n)=O(f(n))
T3(n)=O(g(n))
那么T(n)=T2(n)+T3(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))
c乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
例：
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i);
}
}

int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
}
return sum;
}
整个 cal() 函数的时间复杂度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)
5.几种常见时间复杂度实例分析
粗略分为两类：多项式量级和非多项式量级
其中，非多项式量级只有两个：O(2^n)和O(n!).
我们把时间复杂度为非多项式量级的算法问题叫做NP（非确定多项式）问题。
（当数据规模n越来越大的时候，非多项式时间复杂度的算法式非常低效的算法）

多项式时间复杂度：
a.
O(1)
O(1) 只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。
[只要代码的执行时间不随n的增大而增大，这样代码的时间复杂度我们都记作O(1).
一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。]
b.
O(logn）、O(nlogn)
对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。
例：
i=1;
while (i <= n) {
i = i * 2;
}
第三行是循环执行次数最多的，所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。
实际上，变量i的取值就是一个等比数列。如下：

因此，我们只要知道X值是多少，就知道这行代码的执行次数了。即2^x=n,所以x=log2^n
所以这段代码的时间复杂度就是O(log2^n)
为什么我们把所有的对数阶的时间复杂度都记为O(logn)
**因为对数是可以互相转换的,log3^n就等于log3^2log2^n,所以所以 O(log3n) = O(C * log2n)，其中C=log32 是一个常量.基于我们前面的理论:在采用大O变价复杂度时候,可以忽略系数.即即 O(Cf(n)) = O(f(n))。因此在对数阶时间复杂度的表示方法中,我们忽略对数的'底',统一表示为O(logn).

如果你理解了我前面讲的 O(logn)，那 O(nlogn)就很容易理解了。还记得我们刚讲的乘法法则吗？如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。
c.
O(m+n)和O(m*n)
码的复杂度由两个数据的规模来决定
例：
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}

int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}

return sum_1 + sum_2;
}
由代码可以看出，m和n是表示两个数据规模。我们在无法实现估计m和n谁的量级大，所以在表示复杂度的时候，就不能简单的利用加法法则去省略其中的一个。所以，上面的代码时间复杂度就是O(m+n).
针对这种情况，原来的加法法则就不正确了，我们需要把加法规则改为：T1(m)+T2(n)=O(f(m)+g(n)).
但是乘法法则依旧有效T1(m)*T2(n) = O(f(m) * f(n))。
四、空间复杂度分析
空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}

for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。我们常见的空间复杂度就是 O(n)。

---内容小结
复杂度也叫渐进复杂度，包括空间复杂度和时间复杂度，用来分析算法执行效率与数据规模之间的增长关系。（越是高阶复杂度的算法，执行效率越低）
常用的数据结构和算法的复杂度从低阶到高阶：
O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)

四、四个复杂度分析
最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
平均情况时间复杂度（加权平均时间复杂度/期望时间复杂度）：为了更好表示平均情况下的复杂度
均摊时间复杂度