Python数据结构-排序大O复杂度实现

Question

我们都被告知，在许多语言中，对象的一般情况排序的流行理论限制为 O(n*log(n))。

假设我们有一个列表：

lst = [1,1,2,3,4,5,3,2,3,4,2,1,2,3]

在 Python 中，我最近了解到使用 Counter (from collections import Counter) 而不是字典的一些额外好处，其中键作为列表编号，值作为它们的出现计数器。

coun = Counter(lst) 
print(coun) # ==> Counter({2: 4, 3: 4, 1: 3, 4: 2, 5: 1})

多次显示 () Counter 的构造需要 O(n) 并且与标准 dict 不同，Counter() 有 一些额外的 space 开销 存储每个元素的频率。

当您尝试使用 Counter 时，它通常 returns 按排序顺序输出： .items() 或 .keys()。也许为了方便起见，它在给你结果之前应用了一个快速的 O(logn) 排序，但当你在简单遍历中使用它时，它听起来出乎意料的糟糕：

for i in range(len(lst)):
    if lst[i] not in coun.keys():
        print("element", lst[i], "not found!")

你自然会期望上面的复杂度是 O(n)，就像在标准字典中一样（在 n 个循环中检查存在是 O(1)）。

因此，在不选择代码的情况下，让我们假设 lst[i] not in coun.keys() 的实现复杂度为 O(1)，使用一些 space 开销。

理论上是否可能，在计数器构造期间，这种额外的（对于非常大且独特的列表来说可能非常大）space 开销给我们带来了优势和中型列表（长度 < 1000）以使用额外的 space 为代价获得 O(n) 排序优势。如果以上是可能的，我假设在幕后有一种机制将停止计算每个元素并将它们放入正确的排序顺序，当内存占用打破某个定义的值（如 1Mb）并且 lst[i] not in coun.keys() 变为O(logn).

在这里只是大声思考，因为实际上我们正在使用的很多列表实际上都少于 1000 个元素。

事后思考 1： 另一方面，当 n<1000 时，您可能不会太在意 O(n) 与 O(nlogn)，它几乎不会显着增加潜在的巨大 space 间接费用。

事后思考 2： 看起来 .keys() 保留了插入顺序，由于我的初始数据集不佳，这恰好与排序顺序相同。

然而，是否有可能实现数据结构，在添加计数对象时将其放置在正确的位置？

Answer 1

排序算法的 O(n*log(n)) 下限仅适用于可以通过相互比较对任意对象进行排序的算法。如果你知道你的数据来自一个有限的领域，你可以使用更高效的算法。例如，如果值都是小整数，则可以使用 counting sort 在 O(n) 时间内有效地对数据进行排序。

这是一个示例，可以对仅包含域 0-5 中的整数的序列进行排序，就像您的示例一样。

def sort_0_to_5(data):
    counts = [0, 0, 0, 0, 0, 0]
    for val in data:
        counts[val] += 1
    return [val for val in range(len(counts)) for _ in range(counts[val])]

这在 O(n) 时间内运行并且仅使用常量 space。这是一种非常基本的计数排序，更高级的版本可以对任意对象进行排序，只要它们在域中具有整数键即可。（您只需要对数据进行几次额外传递以进行累积计数，然后以正确的顺序建立输出。）

基数排序等更复杂的算法可以在准线性时间内处理更大的域。但是，您需要考虑时间的方式变得很棘手，因为一旦域开始与数据集的大小相当，处理域大小的代码部分就会变得越不“恒定”。例如，基数排序需要 O(n*log(k)) 时间，其中 k 是域的大小。

不过我要指出，即使您可以找到一种时间复杂度比标准比较排序更好的排序算法，这实际上并不意味着它对您的实际数据更快。除非数据集的规模很大，否则从渐近分析中排除的常数项可能非常重要。您可能会发现实施得很好的 O(n*log(n)) 排序（例如 Python 的 sorted 后面的排序）比您编写的 O(n) 排序执行得更好手动。

Python数据结构-排序大O复杂度实现

Python data structures - sorting big O complexity implementation

python

sorting

big-o