欢迎！ 这是一个记录了HKU的COMP2119：数据结构与算法课程内容的笔记本。 由于本博客重构时间较晚，因此当记录笔记的一切工具准备就绪后，已经进入学期末了。事实上只剩下不到三周就要考这科了。因此本笔记本中的内容会相较于详细记录来讲更有“速通”的感...

递归递归的思路基本就是把一个大问题拆分成相同分量的小问题。 我们来举一个例子吧。 假设你是一个非常懒的总监，你上司给了你100份文件去处理。与其说你自己把所有的文件都处理了，你的做法是： 从100张纸最上面抽一张来处理，然后把剩下的99张推给你的助...

操作次数假设你有一个排序算法等待测试。你发现在一个高配电脑上算法跑了1秒，在一个2000年生产的老电脑上花了10秒。这种情况下你如何判断你的算法是快还是慢？是算法更高效，还是电脑运行速度带来的影响更大？ 我们不能简单地根据运行时间来衡量算法的好坏，因...

本章来介绍一些基础的数据结构。 抽象数据类型与数据结构抽象数据类型 (Abstract Data Type, ADT) 与 数据结构 (Data Structure) 本质上是两码事。抽象数据类型的角度较为宏观，例如“存在一个栈，允许我往里压入元素，...

在上个章节我们了解到，在一个数组中作搜索通常效率感人。如果在一个未排序的数组里做搜索，则时间复杂度为$O(n)$。排序过的数组还好点，可以用二分搜索达成$O(\log(n))$的时间复杂度。 那么哈希与哈希表就是实现更高效增删改查操作的一次尝试。...

树(Tree)数据结构是我们继续学习进阶数据结构的基石。 树首先我们先介绍通用树 (General Trees)，这种树的每个节点可以拥有任意数量的子节点。这种结构常见于文件系统。 那么树这样的数据结构有什么要求吗？ 一个树里面包含这些内...

增删改我们聊的挺多了，但是查该如何去执行呢？ 搜索算法线性搜索 (Linear Search)最简单的查找方式就是线性搜索 (Linear Search) 了。线性搜索的方法非常简单，例如在数组里，我们就从头到尾按照index把整个数组扫一遍。找...

我们已经在第五章介绍了树。这一章我们将目光聚集到二叉搜索树上。 还记得二分搜索的缺点嘛？二分搜索需要在一个排好序的数组上才能使用，而且正如我们之前所说，二分搜索在这种情况下适用于静态数据的搜索，因为一旦我们需要在数组里添加或删除元素，你需要花费$...

还记得如果我们将数据按顺序插入BST会出现什么问题吗？我们的结果会变成一个链表，所有操作退化为 $O(n)$。 本章我们引入平衡树——这些树会在插入或删除过程中自动调整结构，强制保持平衡，从而保证操作复杂度始终是 $O(\log n)$。 AVL ...

排序是计算机科学中最基础也是最重要的问题之一。本章我们将探讨从基础的 $O(n^2)$ 算法到高效的 $O(n \log n)$ 算法，最后再看看神奇的线性排序 $O(n)$。 基础排序算法 ($O(n^2)$)这些算法虽然效率不高，但逻辑简单直观，...