1. 入门篇
1.1. 数据结构与算法的意义
我们的目的是建立时间复杂度、空间复杂度意识，写出高质量的代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现你的价值，完善你的人生。
- 优化代码及设计架构，提升代码性能（非功能性的需求）
- 看待问题的深度，解决问题的角度
- 锻炼大脑思考能力
1.2. 数据结构与算法的重点
数据结构：一组数据的存储结构
↑↓
算法：操作数据的一组方法
学习顺序：
- 复杂度分析：衡量算法执行效率
- 10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树
- 10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
学习要点：
- 来历
- 自身的特点
- 适合解决的问题
- 实际的应用场景
学习技巧：
- 将所学的数据结构和算法自己写一遍，适度刷题
- 多问、多思考、多互动
- 设立目标，打怪升级学习法
- 反复迭代，不断沉淀
1.3. 复杂度分析
为什么需要复杂度分析？
分析、统计算法的执行效率和资源消耗
事后统计方法：依赖测试环境且受数据规模影响
↓
大O复杂度表示法：
渐进时间复杂度，代码执行时间（空间）随数据规模增长的变化趋势
赋值语句执行1次，for循环的条件判断语句执行n次
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
时间复杂度量级：
常见复杂度量级
时间复杂度类型：
// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element) {
if (i >= len) { // 数组空间不够了
// 重新申请一个2倍大小的数组空间
int new_array[] = new int[len*2];
// 把原来array数组中的数据依次copy到new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array复制给array，array现在大小就是2倍len了
array = new_array;
len = 2 * len;
}
// 将element放到下标为i的位置，下标i加一
array[i] = element;
++i;
}
其中 len 初始值为 10 ，但随着调用函数次数 k 的增加，数组不断扩大为 10·2k ，可视为 n
最好时间复杂度
解：直接插入数据的情况即 O(1)最坏时间复杂度
解：数组满后复制数组的情况即 O(n)平均时间复杂度 = 加权/期望时间复杂度 = 每种情况的执行次数 * 发生概率
解：n 种直接插入数据的情况， 1 种数组满后复制数组的情况，等概率为 1/(n+1)
即 1 * 1/(n+1) + … 1 * 1/(n+1) + n * 1/(n+1) = O(1)均摊时间复杂度 = 极特殊的平均时间复杂度
摊还分析法：将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上
解：前 n 次插入数据至数组（O(1)），第 n+1 次复制数组，再插入数据（O(n)），O(1)出现的次数远大于O(n)的次数，均摊得O(1)
