Algorithm
数据结构是指一组数据的存储结构，如队列、栈、堆，算法是操作数据的一组方法，如二分查找、动态规划。
数据结构与算法是相辅相成的，数据结构是为算法服务的，算法需要作用在特定的数据结构上。比如数组具有随机访问的特点，二分查找需要用数组来存储数据，若用链表，二分查找就无法工作了。
十个重要的数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树。
十个重要的算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
对于数据结构和算法，不只是要了解它是什么，更重要的是要知道：它的来历、特点、解决的问题、应用场景。
四种算法思想比较：
- 分治算法解决的问题大部分都不能抽象成多阶段决策问题；贪心、回溯、动态规划解决的问题都可以抽象成多阶段决策。
- 回溯算法是“万金油”，能用动态规划、贪心解决的问题，基本都能用回溯解决，回溯相当于穷举，时间复杂度非常高。
- 动态规划能解决的问题需要满足最优子结构、无后效性、重复子问题三个特性；动态规划高效的原因就是回溯算法中有大量重复子问题，而分治算法相反，要求子问题不能重复。
- 贪心算法本质是动态规划的一种特殊情况，解决问题需要满足最优子结构、无后效性、贪心选择性，不用强调重复子问题。贪心选择性的意思是通过局部的最优选择，能产生全局的最优选择。
Last modified 3yr ago