排序与搜索
快速查找东西
当您搜索 Google 时，结果显示在第二位以下 - 从最相关到最不相关排列。当 Netflix 推荐电影时，它会根据您喜欢的可能性对数千部影片进行排序。每个快速查找和每个排名列表的背后都有一个排序或搜索算法。
为什么排序很重要
排序后的数据是强大的数据。整理好列表后，您可以：
- 使用二分搜索有效地搜索（我们很快就会谈到这一点）。
- 查找重复项 - 他们将坐在彼此旁边。
- 识别前 N 个结果 - 只需获取前 N 个项目。
- 合并数据集 - 组合两个排序列表比组合未排序列表快得多。
冒泡排序 - 简单但速度慢
冒泡排序重复遍历列表，比较相邻的项目，如果顺序错误则交换它们。较大的值会“冒泡”到底。
[5, 3, 8, 1, 2]
↕
[3, 5, 8, 1, 2] → swapped 5 and 3
[3, 5, 1, 8, 2] → swapped 8 and 1
[3, 5, 1, 2, 8] → swapped 8 and 2
... keep going until no swaps needed
时间复杂度：O(n²) - 对于 n 个项目中的每一个，您可以与所有其他项目进行比较。对于 1,000 个项目，最多可进行 1,000,000 次比较。拥有 1,000,000 件物品？一万亿次比较。对于人工智能工作负载来说不实用。
如果冒泡排序大约进行 n2 次比较，那么对 100 万个项目进行排序与对 1000 个项目进行排序相比会慢多少？考虑一下比率：(1,000,000)² 与 (1,000)²。仅仅因为数据量增加了一千倍，速度就慢了一百万倍。
归并排序 - 分而治之
合并排序采用更聪明的方法：将列表分成两半，对每一半进行排序，然后将已排序的两半合并在一起。
[5, 3, 8, 1, 2, 7, 4, 6]
split
[5, 3, 8, 1] [2, 7, 4, 6]
split split
[5, 3] [8, 1] [2, 7] [4, 6]
↓ ↓ ↓ ↓
[3, 5] [1, 8] [2, 7] [4, 6]
merge merge
[1, 3, 5, 8] [2, 4, 6, 7]
merge
[1, 2, 3, 4, 5, 6, 7, 8]
时间复杂度：O(n log n) - 速度显着加快。对于 100 万个商品，大约需要 2000 万次比较，而不是 1 万亿次。这种算法使真正的人工智能系统成为可能。
Python 的内置排序使用 Timsort——一种结合了合并排序和插入排序的混合算法。它由 Tim Peters 于 2002 年发明，现在用于 Python、Java 和 Android。它经过专门设计，可以在通常已部分排序的现实数据上表现良好。
大规模冒泡排序与合并排序
|项目 |冒泡排序 (O(n²)) |归并排序 (O(n log n)) | |--------|---------------------|------------------------| | 100 | 100 10,000 次操作 |约 700 次操作 | | 10,000 | 100,000,000 次操作 |约 130,000 次操作 | | 1,000,000 | 1,000,000,000,000 次操作 |约 20,000,000 次操作 |
这种差异不是学术上的——而是“一秒钟内完成”和“下周完成”之间的差异。
为什么对于人工智能应用中的大型数据集，合并排序优于冒泡排序？
二分查找 - 电话簿技巧
想象一下在电话簿中查找“史密斯”。你不会从第一页开始阅读每个名字。你可以大致从中间打开书，看看你在哪里，然后跳到正确的一半。然后重复。
这就是二分搜索 - 它只适用于排序的数据。
讨论
登录 参与讨论