Video description
课程简介
这套算法视频讲座涵盖算法和数据结构的基本知识,重点是Java实现的应用以及采用科学方法的性能分析,这些知识是所有程序员都应当认真学习的。
描述
本视频全面讲解基本数据类型、算法和数据结构,重点是Java实现的应用以及采用科学方法的性能分析。本视频的配套书籍是《算法》(第4版)——目前算法领域的畅销教材之一。视频讲座的顺序与书中的章节顺序大致相同,但对部分章节进行了重组,从而从不同的视角帮助读者理解书中内容。
如果你还没有《算法》这本书,欢迎立刻下单,在获得纸质版的同时,可获得全部视频讲座的访问链接。
本书的教师网站还提供以下相关资源:
● 全部Java实现
● 测试数据
● 练习题及答案
● 动态可视化演示
● 教学PPT
● 编程作业及检查清单
● 其他相关资源链接
Get技能
你能从视频中学到的知识
本视频介绍了当今最重要的计算机算法。这些算法代表过去50年发展起来的知识体系,它们现在已经成为不可或缺的知识。讲座内容包括:
● 实现有用的算法
● 关于性能特征的详细信息
● 关于客户端和应用的实例
前面几篇讲座涵盖了我们学习算法的基本方法,包括栈、队列和其他低级抽象的数据类型。然后我们将讨论以下主题:
● 排序算法,重点是经典的快速排序和归并排序算法。
● 搜索算法,包括基于平衡搜索树和哈希的搜索方法。
● 字符串处理算法,从字典、子串搜索到正则表达式搜索和数据压缩。
● 图算法,先介绍图搜索、最短路径和最小生成树,然后讲解最大流/最小割及其应用。
● 化简、线性规划和难解性。
Table of Contents
引言
算法:引言
第1讲:union-find
动态连通性
quick-find
quick-union
quick-union的改进
union-find的应用
第2讲:算法分析
算法分析简介
观察
数学模型
根据增长的阶进行分类
算法理论
内存
第3讲:栈和队列
栈
可调数组
队列
泛型
迭代器
栈和队列的应用
第4讲:基本排序方法
排序简介
选择排序
插入排序
希尔排序
洗牌
凸包
第5讲:归并排序
归并排序
自底向上的归并排序
排序的算法复杂性
comparator接口
稳定性
第6讲:快速排序
快速排序
选择
重复键
系统排序
第7讲:优先队列
API和基本实现
二叉堆
堆排序
事件驱动仿真
第8讲:基本符号表
符号表API
基本实现
有序操作
二叉搜索树(BST)
BST中的有序操作
BST中的删除
第9讲:平衡搜索树
搜索树
红黑BST
B树
第10讲:BST的几何应用
搜索范围
线段相交
kd树
区间搜索树
矩形相交
第11讲:哈希表
哈希函数
分离链
线性探测
应用场景
集合
字典客户端
索引客户端
稀疏向量
第12讲:无向图
图简介
图API
深度优先搜索
广度优先搜索
连通分图
图的挑战
第13讲:有向图
有向图简介
有向图API
有向图搜索
拓扑排序
强连通分图
第14讲:最小生成树
MST简介
贪婪算法
加权边图API
Kruskal算法
Prim算法
MST应用场景
第15讲:最短路径
最短路径API
最短路径的性质
Dijkstra算法
加权边DAG
负权值
第16讲:最大流和最小割
最大流简介
Ford-Fulkerson算法
最大流-最小割定理
运行时间分析
Java实现
最大流应用
第17讲:基数排序
Java中的字符串
键索引计算
LSD基数排序
MSD基数排序
3路基数快速排序
后缀数组
第18讲:字典树
R路字典树
三分搜索字典树
基于字符的操作
第19讲:子串搜索
子串搜索简介
蛮力子串搜索
Knuth-Morris-Pratt
Boyer-Moore
Rabin-Karp
第20讲:正则表达式
正则表达式
RE和NFA
NFA模拟
NFA构建
正则表达式应用
第21讲:数据压缩
数据压缩简介
游程编码
霍夫曼压缩
LZW压缩
第22讲:化简
化简简介
设计算法
建立下界
分类问题
第23讲:线性规划
Brewer问题
单纯形算法
单纯形实现
线性规划化简
第24讲:难解性
难解性简介
搜索问题
P和NP
分类问题
NP完全
应对难解性问题