1

我一直对此感到有些困惑，可能是由于我对编译器缺乏了解。但是让我们以 python 为例。如果我们有一些名为 numlist 的大型数字列表，并且想要删除任何重复项，我们可以在列表上使用集合运算符，例如 set(numlist)。作为回报，我们将获得一组数字。据我所知，此操作将在 O(n) 时间内完成。虽然如果我要创建自己的算法来处理这个操作，我所希望的绝对最好的结果是 O(n^2)。

我没有得到的是，是什么允许像 set() 这样的内部操作比语言算法的外部操作快得多。检查仍然需要完成，不是吗？

4

6 回答 6

3

您可以Θ(n)使用哈希表在平均时间内完成此操作。哈希表中的查找和插入是Θ(1)平均的。因此，您只需遍历n项目并检查每个项目是否已经在哈希表中，以及是否没有插入项目。

我没有得到的是，是什么允许像 set() 这样的内部操作比语言算法的外部操作快得多。检查仍然需要完成，不是吗？

如果由语言实现者实现而不是由语言用户实现，算法的渐近复杂度不会改变。只要两者都是用图灵完备的语言和随机存取存储器模型实现的，它们就具有相同的功能，并且在每种语言中实现的算法将具有相同的渐近复杂度。如果一个算法理论上O(f(n))是，不管它是用汇编语言、C#还是 Python 实现都没有关系，它仍然是O(f(n)).

于 2010-02-05T04:05:39.970 回答
1

算法的复杂性界限与它是“内部”还是“外部”实现完全无关

于 2010-02-05T03:46:53.847 回答
1

获取一个列表并将其转换为一个集合set()是 O(n)。

这是因为set它是作为散列集实现的。这意味着检查某个东西是否在集合中或将某些东西添加到集合中只需要 O(1) 恒定时间。因此，要从可迭代对象（例如列表）中创建一个集合，您只需从一个空集合开始，然后逐个添加可迭代对象的元素。由于有 n 个元素并且每次插入需要 O(1)，因此将可迭代对象转换为集合的总时间为 O(n)。

要了解哈希实现的工作原理，请参阅关于哈希表的维基百科文章

于 2010-02-05T03:51:36.353 回答
1

您可以使用任何语言在 O(n) 中执行此操作，基本上如下：

# Get min and max values O(n).

min = oldList[0]
max = oldList[0]
for i = 1 to oldList.size() - 1:
    if oldList[i] < min:
        min = oldList[i]
    if oldList[i] > max:
        max = oldList[i]

# Initialise boolean list O(n)

isInList = new boolean[max - min + 1]
for i = min to max:
    isInList[i] = false

# Change booleans for values in old list O(n)

for i = 0 to oldList.size() - 1:
    isInList[oldList[i] - min] = true

# Create new list from booleans O(n) (or O(1) based on integer range).

newList = []
for i = min to max:
    if isInList[i - min]:
        newList.append (i)

我在这里假设这append是一个 O(1) 操作，除非实施者脑残，否则它应该是。所以每k步O（n），你仍然有一个O（n）操作。

这些步骤是在您的代码中明确完成还是在语言的掩护下完成是无关紧要的。否则，您可以声称 Cqsort是一个操作，并且您现在拥有 O(1) 排序例程的圣杯 :-)

正如许多人所发现的那样，您通常可以用空间复杂度来换取时间复杂度。例如，上面的方法之所以有效，是因为我们可以引入isInListandnewList变量。如果不允许这样做，下一个最佳解决方案可能是对列表进行排序（可能没有更好的 O(n log n)），然后是 O(n)（我认为）操作以删除重复项。

一个极端的例子，你可以使用相同的额外空间方法在 O(n) 时间内对任意数量的 32 位整数（比如每个只有 255 个或更少的重复项）进行排序，前提是你可以为大约 40 亿字节分配存储计数。

只需将所有计数初始化为零并遍历列表中的每个位置，根据该位置的数字递增计数。那是 O(n)。

然后从列表的开头开始遍历 count 数组，将许多正确的值放入列表中。那是 O(1)，当然 1 大约是 40 亿，但仍然是恒定的时间:-)

这也是 O(1) 空间复杂度，但是一个非常大的“1”。通常，权衡并不那么严重。

于 2010-02-05T04:23:19.067 回答
0

我想不出如何在 O(n) 中做到这一点，但这是很酷的事情：

n^2 和 n 之间的差异是如此之大，以至于与用于实现它的算法相比，您实现它和 python 实现之间的差异很小。n^2 总是比 O(n) 差，即使 n^2 是在 C 中，而 O(n) 是在 python 中。您永远不应该认为这种差异来自您不是用低级语言编写的事实。

也就是说，如果你想实现自己的，你可以做一个排序然后删除重复。排序是 n*ln(n) 并且在 O(n) 中删除重复...

于 2010-02-05T03:51:05.553 回答
0

这里有两个问题。

时间复杂度（用大 O 表示法表示）是算法在给定集合大小下运行多长时间的正式度量。它更多的是关于算法的扩展性，而不是绝对速度。

算法的实际速度（例如，以毫秒为单位）是时间复杂度乘以常数（在理想世界中）。

两个人可以以 O(log(n)*n) 的复杂度实现相同的重复删除算法，但是如果一个人用 Python 编写它，另一个用优化的 C 编写它，那么 C 程序会更快。

于 2010-02-05T04:23:08.180 回答