【MIT6.006】【lec3】集合与排序

一、课程介绍与主题回顾

讲师：Justin，6.006课程的第三位讲师。

课程主题：围绕算法设计与分析，重点关注接口（interface）与数据结构（data structure）的区别。

接口：定义了一组操作，但不涉及具体实现。
数据结构：具体实现接口的存储方式，影响效率和性能。

二、集合（Set）接口

定义：集合是一个存储元素的容器，支持插入、查找、删除等操作。

操作：

插入（Insert）：将一个对象加入集合。
查找（Find）：检查某个键值是否存在于集合中。
删除（Delete）：从集合中移除一个对象。
查询（Query）：如查找最小值、最大值等。

示例：学生集合，以学生ID作为键值，其他信息（如姓名、电话等）作为附加数据。

三、实现集合的两种方法

1. 无序数组（Unsorted Array）

实现：将所有元素存储在一个无序数组中。

效率分析：

插入： $O(1)$ ，直接添加到数组末尾。
查找： $O(n)$ ，需要遍历整个数组。
删除： $O(n)$ ，需要查找并移动元素。
查询：如查找最小值，需要遍历整个数组，时间复杂度为 $O(n)$ 。

总结：实现简单，但效率较低。

2. 排序数组（Sorted Array）

实现：将元素按键值排序后存储。

效率分析：

插入： $O(n)$ ，需要找到合适位置并移动元素。
查找： $O(\log n)$ ，使用二分查找。
删除： $O(n)$ ，需要移动元素。
查询：如查找最小值或最大值，时间复杂度为 $O(1)$ 。

总结：查找效率高，但插入和删除操作较慢。

四、排序算法

1. 排列排序（Permutation Sort）

原理：生成所有可能的排列，检查哪一个是有序的。

时间复杂度：至少为

O(n! \times n)

，因为有

n!

种排列，每种排列需要

O(n)

时间检查。

总结：理论上正确，但效率极低，不实用。

2. 选择排序（Selection Sort）

原理：每次从未排序部分选择最大（或最小）元素，放到已排序部分的末尾。

实现：

找到数组中最大元素的索引。
将最大元素与数组末尾的元素交换。
对剩余部分递归排序。

时间复杂度：

O(n^2)

，因为每轮需要

O(n)

时间找到最大值，共

n

轮。

证明：

递归关系： $T(n) = T(n-1) + O(n)$ 。
解：通过代换法，假设 $T(n) = O(n^2)$ ，验证符合递归关系。

3. 归并排序（Merge Sort）

原理：分治法，将数组分成两半，分别排序，然后合并。

实现：

将数组分成两半，分别递归排序。
合并两个已排序的子数组。

合并步骤：

使用“双指针”技术，从两个子数组的末尾开始，逐个比较并合并。
时间复杂度为 $O(n)$ 。

时间复杂度：

O(n \log n)

。

递归关系： $T(n) = 2T(n/2) + O(n)$ 。
解：通过代换法，假设 $T(n) = O(n \log n)$ ，验证符合递归关系。

五、总结

接口与数据结构：选择合适的数据结构来实现接口，是算法设计的关键。

排序算法：

排列排序：理论上正确，但效率极低。
选择排序：简单易实现，但时间复杂度为 $O(n^2)$ 。
归并排序：高效排序算法，时间复杂度为 $O(n \log n)$ ，适合大规模数据排序。

2025-03-12 数学