高级数据结构与算法分析

课程简介

高级数据结构与算法分析 Advanced Data Structure & Algorithm Analysis，简称 ADS 。

课程内容分为两部分：

• 高级数据结构

主要包括包括用于查找的二叉搜索树的各种变形（AVL树、Splay树、红黑树、B+树）、倒排索引表、优先队列的各种优化结构（左式堆、斜堆和二项堆）等。

• 算法分析

主要包括摊还分析、回溯、分治、动态规划、贪心、NP问题，以及近似算法、局部搜索、随机算法等；随后介绍并行算法以及外部排序。

相较于数据结构，算法分析占据更主要的位置且难度更大。特别是 NP 问题、近似算法、局部搜索、随机算法等理论性强的章节等在考试时难度偏高，其中很多问题直到目前也受到众多理论计算机科学家的关心。