admin管理员组文章数量:1625101
写在开头
这是一篇读书笔记式的文章，力求简要地概括《算法图解》 中陌生和重要的内容，所以有的具体内容仍需要参考原书。
值得记录的代码附在文末，使用python编写。
持续更新。
这本书已经读完，这篇笔记也更新至此。不得不说，《算法图解》是一本对新手非常友好的书，内容详细而不啰嗦，十分有条理，只要沿着顺序读下去，基本能够很快理解消化。我很庆幸我是在这本书中第一次接触到诸如动态规划之类的知识点，否则很有可能又被劝退了。当然，由于其篇幅限制，很多常用内容没有介绍到，还需要继续补充，这些内容记录在我的另一篇笔记里。
第1章 算法简介
二分查找
大O表示法：O(n)，n指操作数
- 该表示法中的log默认以2为底
- 指出了算法运行时间的增速
- 画16个格子的例子：一个一个画，O(n)；四次对折，O(logn)
- 指出的是最糟情况下的操作数
常见的大O运行时间
- O(log n)
- O(n)
- O(n*log n)
- O(n^2)
- O(n!)，如旅行商问题
随着输入的增加，上述五种算法的操作数的增加由慢到快
第2章 选择排序
数组与链表的区别：“挨着坐”和“分开坐”
数组在内存中是连续存放的；链表中的元素可以存储在内存的任何地方，链表的每个元素都存储了下一个元素的地址。
数组vs链表
- 当数组增加元素而相邻内存单元已被占用，就需要移动整个数组，链表不存在这个问题
- 需要读取链表最后一个元素时，需要从第一个开始依次读取。当需要同时读取所有元素时，链表效率高，需要跳跃时效率低；数组相反
- 数组支持随机访问，链表只能顺序访问
一个疑惑和其解答
Q：在向链表的中间插入元素时，不需要先从第一个元素逐个获取索引，直到要插入的位置？
A：获取索引即读的过程，不应算在操作数中；只考虑插入这个操作。
数组与列表可以组合使用
facebook存储用户信息的例子
TODO：选择排序的例子，为什么是使用平均每次检查的操作数的平均值来计算O，而不是直观理解的阶乘？
第3章 递归
性能
递归并不会比循环提高性能，但可能更容易理解
组成
- 基线条件：控制何时停止调用自己，避免无限循环
- 递归条件：循环调用自己
栈
只对最上层元素执行两种操作：插入、删除并读取（弹出）
调用栈
例子的文字总结：一个函数A中调用了另一个函数B，当A开始执行，内存分配给其一部分，存储其涉及到的所有变量；当执行到B，内存分配给B一部分，并在栈中压在A的部分之上；执行B，其被从栈上弹出，此时A位于最上方，故继续执行A。这个用于储存多个函数的变量的栈，被称为调用栈。
调用另一个函数时，当前函数暂停并处于未完成状态。
递归调用栈：以阶乘为例
要注意，一个变量在每次调用中的值可能不同，在一个调用中不能访问另一个调用中的变量（还是比较符合常识的）
栈的弊端
每次函数调用会占用内存，栈过高占用的内存也过多
解决办法：改用循环；使用尾递归（本书不涉及）
第4章 快速排序
分而治之，Divide and Conquer,D&C
- 找出尽可能简单的基线条件
- 不断将问题分解直到满足基线条件
Tip：涉及到数组的递归函数常见的基线条件是数组为空或只含一个元素。
快速排序思路
- 最简单的排序：不需要排序，即数组中只有0或1个元素
- 两个元素的数组，比较二者的值
- 多于两个元素的数组，分而治之
- 选取一个元素作为基准值（暂取第一个）
- 分区：遍历，找出比基准值大的和小的元素，分别构成两个数组。目前有：比基准值小的子数组、基准值、比基准值大的子数组
- 对子数组递归，直到剩下的数组长度小于等于二
- 子数组排序后，合并
使用python实现的快排，见代码1
再谈大O表示法 - 比较合并排序和快速排序 - 大O表示法中的常量
例子，逐个打印数组元素的函数，一个没有sleep(1)（记一次sleep的时间为c），另一个有，则其运行时间分别为c*n和n。但是在大O表示法中，固定时间量，也即常数c，是忽略不计的，因为一般来说对时间影响更大的是n和logn的区别。
对于运行时间都为nlogn的快速查找和合并查找，常量的影响就可能很大；快速查找更快
版权声明：本文标题：《算法图解》笔记与总结 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/xitong/1728922970a1180025.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论