【学习笔记】《数据结构与算法之美》入门篇【学习笔记】《数据结构与算

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)