时间复杂度:指的是算法随着输入量增大,运行时间的增长率

常见的几种大O记法:O(logN)、O(N)、O(NlogN)、O(N^2)、O(N!)

插入排序中提到了链表和数组,是最基础的数据结构,比如Java的HashMap就涉及到了链表和数组。理解这两个在插入、删除和查找操作的时间复杂度比较。有一个点是关于计算机内存的物理结构部分,一个基本类型在内存中怎么表示,数组又是怎么表示,链接在内存中是怎么存在的。一方面。理解数据结构的逻辑结构,但也要明白它们的物理存储形式。

递归的概念:函数调用自身。基线和递归项的形式是很优美的,不能把基准条件漏了,否则立马Java爆栈。这里涉及到了一个数据结构:栈,?#22270;?#31639;机中的基本部分:函数调用在计算机中是怎么实现的,参考《深入理解计算机系统》相关部分。

快排:?#31181;?#21644;递归怎么理解?递归是一种实现,?#31181;?#26159;一种策略。这里?#31181;?#26159;把原问题分解成两部分子问题,然后利用递归操作子问题。快排的平均时间复杂度是O(NlogN),但在最?#30331;?#20917;:?#34892;潁?#27491;序或逆序)变成了O(N^2)。这里一个关键优化部分是怎么选择pivot,可参?#20960;?#29702;论化的算法书籍:《数据结构与算法分析:C语言描述》《算法导论》

哈希表在各种语言中属于常用的集合。Java中的HashMap、HashTable,Python中的字典等,JSON数据格式也是。关键词:hash函数计算索引,解决冲突的方法:链或者再次哈希等,负载因子(load factor)进行resize操作。

BFS:最好理解的是用链表来连接邻居,这样在当前元素出队时,?#36816;?#30340;邻居们进行遍历入队操作就好理解了。队列在BFS中是作为?#36816;?#26377;元素进行遍历的结构,从起点入队开始,循?#20998;?#21040;队?#24418;?#31354;,循环中对当前出队元素的邻居们进行入队操作以及附?#20248;?#26029;。运行时间怎么理解是O(V+E),首先是?#36816;?#26377;节点进行遍历一次,在访问邻居时,相当于把从当前节点到它所有邻居节点通过边访问一次,这就是时间复杂度的来?#30784;?/p>

Dijkstra算法是针对DAGs(有向无环图)求解单源最短路径。每一次循环找还没有处理的节点中距离最短的节点,关键操作:从起点到当前节点的邻居节点的距离,能不能通过当前节点中转减少距离,即不直接到达,先到当前节点再到邻居节点的距离和是不是比直接到达的距离小,若小,则更新最短距离。这里怎么保证最终是最优的呢?用BFS来看,从起点的第一步可达的开始,就更新最短距离,慢慢扩大起点经过两条边到达的节点,最后的是最最优的。保证前面每一步是最优更新。至于是属于动态规划还是贪心,?#19968;?#27809;理解。。。

贪心算法:经典的区间问题?#22909;?#19968;次都选择当前最优,这里是区间结束最早的时间段,这样最后最优。但不是所有都是最优。set-convering problem昨天一直在纠结它的时间复杂度问题,我的理解是直接解法:O(2^n),贪心:O(m*n)(m是state数,是station数),而书中给出是如下 enter image description here

动态规划:0-1背包问题采用的图解方法是最好理解,后面的公式也是来的水到渠成,推荐这一部分。最长公共子序列就不明白了。。。

KNN?#21644;?#20840;是多余的部分,严格来说不是机器学习算法,没有经过train和test,建议参考李航博士《统计学习方法》,第二版也出版了,?#34892;?#36259;的可以购进。我是读到SVM部分就挂,那些个数学公式涉及的优化部分看不太懂。

最后?#21644;?#33616;了几颗树(红黑树、二叉搜索树等),倒排索引,傅里叶变换(让我想起了V2的一个帖子),并行算法不知道说了啥,MapReduce,好吧我再?#30053;?#19968;次,做好准备再看,其它的我就不说了。

整本书,Github上有其它语言的实现,我以为只有Python,虽然Python也能写,但是懒?#20040;?#24320;Pycharm。

我一直看的是原理和时间复杂度,没怎么注意代码,书刷过到LeetCodo刷题吧。

随便写的笔记,是自己的理解,有一些还是有问题不完全理解,?#38431;?#25351;出。