读书笔记：极客时间数据结构与算法之美的学习笔记.zip

# AlgorithmStudy 极客时间-数据结构与算法之美的学习笔记 ### 3.复杂度分析（上） 1.大O表示法：T(n)=O(f(n))，表示变化趋势 ​ T(n)：代码执行的时间 ​ f(n)：每行代码执行的次数综合 ​ 只取最大量级来表示：T(n)=O(2n²+2n+3)=>T(n)=n² 2.如何分析一段代码的时间复杂度 ​ 只关注循环次数最多的一段代码 ​ 总的时间复杂度等于量级最大的那段代码的时间复杂度 ​ 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 3.常见复杂度量级 多项式量级： - 常量阶：O(1) - 对数阶：O(logn) - 线性阶：O(n) - 线性对数阶：O(nlogn) - 平方阶：O(n²)、立方阶：O(n³)、k次方阶：O(nk) 非多项式量级： - 指数阶：O(2n²) - 阶乘阶：O(n!) ### 4.复杂度分析（下） 1.最好情况时间复杂度 2.最坏情况时间复杂度 3.平均情况时间复杂度（加权平均时间复杂度/期望时间复杂度） 4.均摊时间复杂度（连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这时候就可以看是否能将较高时间复杂度那次操作的耗时平摊到其他那些时间复杂度比较低的操作上，一般平摊时间复杂度就等于最好时间复杂度） ### 5.数组：为什么很多编程语言中数组都从0开始编号 1.数组支持随机访问（a[i]_address=base_address+i*data_type_size），根据下标随机访问的时间复杂度为O(1) 2.数组与List的比较 - List无法存储基本类型，只能使用包装类，有一定的性能损耗 - 数据大小事先已知，且用不到List提供的大部分方法时，可以用数组 - 当要表示多维数组时，往往数组比较直观 - 业务开发使用容器就可以，损耗一点点性能无伤大雅 3.为什么很多编程语言中数组都从0开始编号？ - 从0开始时a[k]内存计算：a[k]_address=base_address+k*data_type_size，从1开始编号时：a[k]_address=base_address+(k-1)*data_type_size，多了一次减法指令 - 历史原因：C语言设计者用0开始计数数组下标，之后的高级语言都效仿了C语言 ### 6.链表（上）：如何实现LRU缓存淘汰算法 1.数组需要一块连续的内存空间来存储，当剩余空间大于申请值但是空间并不连续时也会申请失败 2.链表天然支持动态扩容 3.常见链表结构：单链表、双向链表、循环链表、双向循环链表 - 单链表：->data,next->data,next->data,next->NULL - 每个节点都有data和后继指针next，尾节点指向NULL - 插入删除复杂度0(1)，随机访问第n个元素需要从头到尾查找复杂度O(n) - 循环链表 - 尾节点指针指向头节点 - 双向链表 - ->prev,data,next-><-prev,data,next-><-prev,data,next-><-prev,data,next 4.cpu在内存中读取数据的时候，会先把读取到的数据加载到cpu缓存中，而cpu每次从内存中读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块并保存到cpu缓存中，下次访问的时候会先从缓存中找，找到了就不用去内存中取，这样就实现了比内存访问速度更快的机制，而数组内存是连续的，所以在加载某个下标的元素时会把接下去的元素也加载进去，这样执行速度会比内存地址不连续的链表快 5.如果字符串是用单链表来存储的，怎么判断它是一个回文串？ - 快慢指针，快指针一次走两步，慢指针一次走一步，当快指针到尾巴的时候慢指针就在中间点 - 慢指针在走的同时反转节点指向 - 再起一个指针和中间点的指针一次走并比较 - 时间复杂度O(n)，空间复杂度O(1) ### 7.链表（下）：如何轻松写出正确的链表代码 1.理解指针或引用的含义 2.警惕指针丢失和内存泄漏 3.利用“哨兵”简化实现难度 4.重点留意边界条件处理 5.举例画图，辅助思考 6.多写多练，没有捷径 7.5个常见的链表操作：单链表反转、链表中环检测、两个有序链表合并、删除链表倒数第n个节点、求链表的中间节点 ### 8.栈：如何实现浏览器的前进和后退功能？ 1.后进先出，先进后出 2.用数组实现的栈叫“顺序栈”，用链表实现的栈叫“链式栈” 3.空间复杂度是指除了原本的数据存储空间外，算法运行还需要额外的存储空间 4.用栈实现表达式求值：34+13*9+44-12/3，使用两个栈来实现，一个栈保存操作数，一个栈保存运算符，从左到右遍历，遇到数字压入操作数栈，遇到操作符就与操作栈顶元素比较，如果比栈顶元素优先级高，就将当前运算符压入操作符栈，当优先级低或者相同，从运算符栈顶取出运算符，从操作数栈顶取2个操作数进行计算，计算值压入操作数栈，继续比较 ### 9.队列：队列在线程池等有限资源池中的应用 1.先进先出，入队enqueue()，出队dequeue() 2.数组实现的叫顺序队列，链表实现的叫链式队列 3.避免数据迁移可以使用循环队列，判断队列满的条件：(tail+1)%n=head 4.阻塞队列、并发队列 5.线程池的实现策略，在线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何实现 - 非阻塞的处理方式，直接拒绝任务 - 阻塞的处理方式，请求排队，等到有空闲线程时，取出队列的请求继续处理 - 基于链表实现无限排队的无界队列，会导致过多的请求排队等待，请求处理的响应时间过长不适合对响应时间敏感的系统 - 基于数组实现的有界队列，排队超过队列大小时，接下去的请求会被拒绝，适合对响应时间敏感的系统，设置一个合适的队列大小很重要 6.如何实现无锁并发队列？使用[CAS](https://www.jianshu.com/p/ae25eb3cfb5d)（比较和交换（Conmpare And Swap））实现，入队前获取tail位置，入队时比较tail是否发生变化，如果否则允许入队，反之则入队失败，出队则是获取head位置，进行CAS ### 10.递归：如何用三行代码找到“最终推荐人” 1.递归需要满足三个条件 - 一个问题的解可以分解为几个子问题的解 - 这个问题与分解之后的子问题，除了数据规模不一同，求解思路完全一样 - 存在递归的终止条件 2.写递归代码要找到如何将大问题分解为小问题的规律，并基于此写出地推公式，再推敲终止条件，最终翻译成代码 3.递归弊端：堆栈溢出、重复计算、函数调动耗时多、空间复杂度高等 4.走台阶问题：总共n个台阶，每次可以走1个或者2个台阶，总共有多少种走法 - 第一步可以走1步或者2步，剩下(n-1)个台阶的走法加上剩下(n-2)个台阶的走法 - 递推公式：f(n)=f(n-1)+f(n-2) - 终止条件为f(1)=1--走1步，和f(2)=2--走2个1步或者1个2步 ~~~java int f (int n) { if (n == 1) return 1; if (n == 2) return 2; return f(n-1) + f(n+2); } ~~~ ### 11.排序（上）：为什么插入排序比冒泡排序更受欢迎 1.常见排序 | 排序算法 | 时间复杂度 | 是否稳定排序 | 是否原地排序 | | -------- | ------------------ | ------------ | ------------ | | 冒泡排序 | O(n²) | ✔️ | ✔️ | | 插入排序 | O(n²) | ✔️ | ✔️ | | 选择排序 | O(n²) | ❌ | ✔️ | | 快速排序 | O(nlogn) | ❌ | ✔️ | | 归并排序 | O(nlogn) | ✔️ | ❌ | | 计数排序 | O(n+k) k是数据范围 | ✔️ | ❌ | | 桶排序 | O(n) | ✔️ | ❌ | | 基数排序 | O(dn) d是维度