48

在讨论涉及散列和搜索类型的算法时，我注意到 O(1) 的一些非常奇怪的用法，通常是在使用语言系统提供的字典类型或使用数组使用的字典或散列数组类型的上下文中-索引符号。

基本上，O(1) 意味着以恒定时间和（通常）固定空间为界。一些非常基本的操作是 O(1)，尽管使用中间语言和特殊 VM 往往会扭曲这里的想法（例如，如何将垃圾收集器和其他动态过程摊销到 O(1) 活动中）。

但是忽略延迟、垃圾收集等的摊销，我仍然不明白如何假设某些涉及某种搜索的技术可以是 O(1)，除非在非常特殊的条件下。

尽管我之前已经注意到这一点，但Pandincus 问题中刚刚出现了一个示例，“'Proper' collection to use to get items in O(1) time in C# .NET?” .

正如我在那里所说，我所知道的唯一提供 O(1) 访问作为保证边界的集合是具有整数索引值的固定边界数组。假设是该数组是通过一些映射到随机存取存储器来实现的，该映射使用 O(1) 操作来定位具有该索引的单元格。

对于涉及某种搜索以确定不同类型索引（或具有整数索引的稀疏数组）的匹配单元格位置的集合，生活并不容易。特别是，如果存在冲突并且可能出现拥塞，则访问不完全是 O(1)。而且，如果集合是灵活的，则必须认识到并摊销扩展底层结构（例如树或哈希表）的成本，以缓解拥塞（例如，高碰撞发生率或树不平衡）。

我从来没有想过将这些灵活和动态的结构称为 O(1)。然而，我看到它们作为 O(1) 解决方案提供，而没有任何确定必须保持的条件才能确保实际具有 O(1) 访问（并且该常数小到可以忽略不计）。

问题：所有这些准备都是为了一个问题。O(1) 周围的随意性是什么？为什么如此盲目地接受它？是否认识到即使 O(1) 也可能非常大，即使接近恒定？还是 O(1) 只是将计算复杂性概念用于非正式使用？我很困惑。

更新：答案和评论指出了我自己定义 O(1) 的随意之处，我已经修复了它。我仍在寻找好的答案，在某些情况下，一些评论线程比他们的答案更有趣。

4

13 回答 13

61

问题是人们对术语真的很草率。这里有 3 个重要但不同的类：

O(1) 最坏情况

这很简单 - 在最坏的情况下，所有操作都不会超过恒定的时间，因此在所有情况下都是如此。访问数组的元素是O(1)最坏的情况。

O(1) 摊销最坏情况

摊销意味着不是每个操作都O(1)处于最坏情况，但是对于任何 N 个操作的序列，序列的总成本O(N)在最坏情况下是 no。这意味着即使我们不能将任何单个操作的成本限制为常数，但总会有足够的“快速”操作来弥补“慢”操作，使得操作序列的运行时间是线性的在操作次数上。

例如，标准的动态数组在填满时会增加一倍的容量，需要O(1)分摊的时间才能在最后插入一个元素，即使某些插入需要O(N)时间 - 总是有足够的O(1)插入，插入 N 项总是需要O(N)时间。

O(1) 平均情况

这个是最棘手的。平均情况有两种可能的定义：一种用于具有固定输入的随机算法，另一种用于具有随机输入的确定性算法。

对于具有固定输入的随机算法，我们可以通过分析算法并确定所有可能运行时间的概率分布并取该分布的平均值来计算任何给定输入的平均情况运行时间（取决于算法，这可能或由于停机问题，可能无法实现）。

在另一种情况下，我们需要输入的概率分布。例如，如果我们要测量一种排序算法，一个这样的概率分布将是所有 N! 输入的可能排列同样可能。然后，平均案例运行时间是所有可能输入的平均运行时间，由每个输入的概率加权。

由于这个问题的主题是确定性的哈希表，因此我将重点关注平均情况的第二个定义。现在，我们不能总是确定输入的概率分布，因为，我们可以对任何东西进行散列，而这些项目可能来自用户在文件系统中输入或来自文件系统。因此，在谈论哈希表时，大多数人只是假设输入行为良好并且哈希函数行为良好，使得任何输入的哈希值基本上随机均匀分布在可能的哈希值范围内。

花点时间，让最后一点深入人心 -O(1)哈希表的平均情况性能来自假设所有哈希值是均匀分布的。如果违反了这个假设（通常不会，但它肯定可以而且确实发生了），则运行时间不再O(1)是平均水平。

另请参见算法复杂性拒绝服务。在本文中，作者讨论了他们如何利用两个版本的 Perl 使用的默认散列函数中的一些弱点来生成大量具有散列冲突的字符串。有了这个字符串列表，他们向一些网络服务器提供了这些字符串，从而在O(N)网络服务器使用的哈希表中产生了最坏情况的行为，从而对一些网络服务器产生了拒绝服务攻击。

于 2008-12-02T05:09:53.750 回答
40

我的理解是 O(1) 不一定是恒定的；相反，它不依赖于所考虑的变量。因此，相对于散列中的元素数量，可以说散列查找是 O(1)，但相对于被散列的数据的长度或散列中元素与桶的比率而言，它不是 O(1)。

另一个令人困惑的因素是大 O 符号描述了限制行为。因此，对于小 N 值的函数 f(N) 可能确实显示出很大的变化，但是如果 N 接近无穷大时的极限相对于 N 是恒定的，那么说它是 O(1) 仍然是正确的。

于 2008-12-02T03:38:51.017 回答
19

O(1) 表示恒定时间和（通常）固定空间

只是为了澄清这是两个单独的陈述。您可以在时间上拥有 O(1)，但在空间上可以拥有 O(n) 或其他任何东西。

是否认识到即使 O(1) 也可能非常大，即使接近恒定？

O(1) 可能是不切实际的巨大，它仍然是 O(1)。经常被忽略的是，如果您知道您将拥有一个非常小的数据集，则常数比复杂性更重要，对于相当小的数据集，它是两者的平衡。如果数据集的常数和大小具有适当的规模，则 O(n!) 算法可以胜过 O(1)。

O() 表示法是对复杂性的度量——而不是算法将花费的时间，或者是对给定算法对于给定目的有多“好”的纯粹度量。

于 2008-12-02T04:03:51.183 回答
11

我明白你在说什么，但我认为哈希表中的查找具有 O(1) 的复杂性的说法有几个基本假设。

  • 哈希函数设计合理，避免大量冲突。
  • 这组键几乎是随机分布的，或者至少不是故意设计为使散列函数性能不佳。

哈希表查找的最坏情况复杂度是 O(n)，但鉴于上述 2 个假设，这极不可能。

于 2008-12-02T03:39:56.537 回答
8

Hashtables是一种支持 O(1) 搜索和插入的数据结构。

哈希表通常有一个键值对，其中键被用作函数（哈希函数）的参数，该函数将确定值在其内部数据结构（通常是数组）中的位置。

由于插入和搜索仅取决于哈希函数的结果，而不取决于哈希表的大小或存储的元素数量，因此哈希表具有 O(1) 的插入和搜索。

但是，有一个警告。也就是说，随着哈希表变得越来越满，将会出现哈希冲突，哈希函数将返回一个已经被占用的数组元素。这将需要解决冲突才能找到另一个空元素。

当发生哈希冲突时，无法在 O(1) 时间内执行搜索或插入。但是，良好的冲突解决算法可以减少尝试寻找另一个合适的空白点的次数，或者增加哈希表的大小可以首先减少冲突的数量。

因此，理论上，只有由具有无限数量元素的数组和完美哈希函数支持的哈希表才能实现 O(1) 性能，因为这是避免哈希冲突导致数量增加的唯一方法所需的操作。因此，对于任何有限大小的数组，由于哈希冲突，有时会小于 O(1)。

让我们看一个例子。让我们使用哈希表来存储以下(key, value)对：

  • (Name, Bob)
  • (Occupation, Student)
  • (Location, Earth)

我们将使用一个包含 100 个元素的数组来实现哈希表后端。

将用于确定要存储 ( , ) 对key的数组元素。为了确定元素，将使用：keyvaluehash_function

  • hash_function("Name")返回18
  • hash_function("Occupation")返回32
  • hash_function("Location")返回74。

根据上面的结果，我们将这些(key, value)对分配给数组的元素。

array[18] = ("Name", "Bob")
array[32] = ("Occupation", "Student")
array[74] = ("Location", "Earth")

插入只需要使用哈希函数，不依赖于哈希表的大小，也不依赖于其元素，因此可以在 O(1) 时间内完成。

类似地，搜索元素使用散列函数。

如果我们想查找 key "Name"，我们将执行 ahash_function("Name")以找出所需值所在的数组中的哪个元素。

此外，搜索不依赖于哈希表的大小或存储的元素数量，因此是 O(1) 操作。

一切都很好。让我们尝试添加一个额外的条目("Pet", "Dog")。但是，有一个问题，因为hash_function("Pet")返回18，它与"Name"键的哈希值相同。

因此，我们需要解决这个哈希冲突。假设我们使用的哈希冲突解决函数发现新的空元素是29：

array[29] = ("Pet", "Dog")

由于在此插入中存在哈希冲突，因此我们的性能并不是 O(1)。

当我们尝试搜索 key 时也会出现这个问题，因为尝试通过 perform 查找包含key"Pet"的元素最初总是返回 18。"Pet"hash_function("Pet")

一旦我们查找元素 18，我们将找到键"Name"而不是"Pet". 当我们发现这种不一致时，我们需要解决冲突以检索包含实际"Pet"键的正确元素。解决哈希冲突是一个额外的操作，它使哈希表在 O(1) 时间不执行。

于 2008-12-02T04:01:10.580 回答
4

我无法谈论您看到的其他讨论，但至少有一种哈希算法可以保证为 O(1)。

Cuckoo 散列保持不变，因此散列表中没有链接。插入摊销 O(1)，检索总是 O(1)。我从未见过它的实现，这是我在大学时新发现的东西。对于相对静态的数据集，应该是一个非常好的O(1)，因为它计算了两个hash函数，执行了两次查找，马上就知道了答案。

请注意，这是假设哈希计算也是 O(1)。您可能会争辩说，对于长度为 K 的字符串，任何散列至少为 O(K)。实际上，您可以很容易地绑定 K，例如 K < 1000。对于 K < 1000，O(K) ~= O(1)。

于 2008-12-02T04:49:03.293 回答
4

关于您如何理解 Big-Oh 表示法可能存在概念错误。这意味着，给定一个算法和一个输入数据集，当数据集的大小趋于无穷大时，算法运行时间的上限取决于 O 函数的值。

当有人说算法需要 O(n) 时间时，这意味着算法最坏情况的运行时间线性地取决于输入集的大小。

当一个算法花费 O(1) 时间时，唯一的意思是，给定一个计算函数 f(n) 运行时间的函数 T(f)，存在一个自然正数 k，使得 T(f) < k 对于任何输入 n。本质上，这意味着算法运行时间的上限不依赖于其大小，并且具有固定的有限限制。

现在，这并不意味着限制很小，只是它与输入集的大小无关。因此，如果我人为地为数据集的大小定义一个边界 k，那么它的复杂度将是 O(k) == O(1)。

例如，在链表上搜索一个值的实例是一个 O(n) 操作。但是如果我说一个列表最多有 8 个元素，那么 O(n) 变为 O(8) 变为 O(1)。

在这种情况下，我们使用 trie 数据结构作为字典（字符树，其中叶节点包含用作键的字符串的值），如果键是有界的，那么它的查找时间可以认为是 O( 1) （如果我将一个字符字段定义为长度最多为 k 个字符，这在许多情况下可能是一个合理的假设）。

对于哈希表，只要假设哈希函数良好（随机分布）且足够稀疏以最大限度地减少冲突，并且在数据结构足够密集时执行重新哈希，您确实可以将其视为 O(1 ) 访问时间结构。

总之，O(1) 时间对于很多事情可能被高估了。对于大型数据结构，足够的散列函数的复杂性可能不是微不足道的，并且存在足够的极端情况，其中冲突的数量导致其表现得像 O(n) 数据结构，并且重新散列可能变得非常昂贵。在这种情况下，像 AVL 或 B-tree 这样的 O(log(n)) 结构可能是更好的选择。

于 2008-12-02T05:00:08.090 回答
2

相对于表中的项目数，HashTable 查找是 O(1)，因为无论您将多少项目添加到列表中，散列单个项目的成本几乎相同，并且创建散列会告诉你是物品的地址。

要回答为什么这是相关的：OP 询问为什么 O(1) 似乎如此随意地被扔掉，而在他看来，它显然不适用于许多情况。这个答案解释了在这种情况下 O(1) 时间确实是可能的。

于 2008-12-02T03:32:56.770 回答
2

总的来说，我认为人们比较使用它们而不考虑准确性。例如，基于散列的数据结构是 O(1)（平均）查找，如果设计得当并且你有一个好的散列。如果所有内容都散列到一个桶中，则为 O(n)。一般来说，虽然一个人使用了一种很好的算法并且密钥分布合理，所以在没有所有条件的情况下将其称为 O(1) 是很方便的。列表、树等也是如此。我们想到了某些实现，并且在讨论一般性时谈论它们更方便，没有限定。另一方面，如果我们正在讨论具体的实现，那么更精确可能是值得的。

于 2008-12-02T03:46:11.890 回答
1

哈希表实现在实践中并不是“完全”使用 O(1)，如果您测试一个，您会发现它们平均大约 1.5 次查找以在大型数据集中找到给定键

（由于确实会发生碰撞，并且在发生碰撞时，必须分配不同的位置）

此外，在实践中，HashMap 由具有初始大小的数组支持，即当它平均达到 70% 的填充度时“增长”到两倍大小，这提供了相对良好的寻址空间。70% 充满后，碰撞率增长得更快。

大 O 理论指出，如果你有一个 O(1) 算法，甚至是一个 O(2) 算法，关键因素是输入集大小与插入/获取其中一个的步骤之间的关系程度。O(2) 仍然是常数时间，所以我们只是将其近似为 O(1)，因为它或多或少意味着相同的事情。

实际上，只有一种方法可以使用 O(1) 获得“完美哈希表”，这需要：

  1. 一个全局完美哈希密钥生成器
  2. 无界寻址空间。

（例外情况：如果您可以预先计算系统允许的键的所有排列，并且您的目标后备存储地址空间被定义为它可以容纳所有允许的键的大小，那么您可以拥有一个完美的散列，但它是“域受限”的完美）

给定一个固定的内存分配，至少有这个是不合理的，因为它会假设你有一些神奇的方法可以将无限量的数据打包到一个固定的空间而不丢失数据，这在逻辑上是不可能的.

所以回想起来，在有限的内存中得到仍然是常数时间的 O(1.5)，即使是相对幼稚的哈希密钥生成器，我认为非常棒。

后缀注释注意我在这里使用 O(1.5) 和 O(2)。这些实际上在 big-o 中不存在。这些只是那些不知道大人物的人认为的基本原理。

如果某物需要 1.5 步才能找到一个密钥，或者 2 步才能找到那个密钥，或者 1 步才能找到那个密钥，但步数永远不会超过 2，并且是 1 步还是 2 步是完全随机的，那么它仍然是O(1) 的大 O。这是因为无论您将多少项目添加到数据集大小，它仍然保持 <2 步骤。如果对于所有表 > 500 个键，它需要 2 个步骤，那么您可以假设这 2 个步骤实际上是一个包含 2 个部分的步骤，......这仍然是 O(1)。

如果你不能做出这个假设，那么你根本就不是 Big-O 思维，因为你必须使用代表完成所有事情所需的有限计算步骤数的数字，而“一步”对你来说毫无意义。只要进入你的脑海， Big-O 和所涉及的执行周期数之间没有直接关联。

于 2008-12-02T03:52:11.067 回答
1

O(1) 确切地说，算法的时间复杂度受一个固定值的限制。这并不意味着它是恒定的，只是它是有界的，无论输入值如何。严格来说，许多据称为 O(1) 的时间算法实际上并不是 O(1)，而且运行速度非常慢，以至于它们受限于所有实际输入值。

于 2008-12-02T06:12:55.620 回答
1

是的，垃圾收集确实会影响在垃圾收集领域中运行的算法的渐近复杂度。它并非没有成本，但如果没有经验方法，很难分析，因为交互成本不是组合成本。

垃圾收集所花费的时间取决于所使用的算法。通常，现代垃圾收集器会在内存填满时切换模式以控制这些成本。例如，一种常见的方法是在内存压力较低时使用 Cheney 样式的复制收集器，因为它付出与活动集大小成正比的成本以换取使用更多空间，并在内存压力时切换到标记和清除收集器变得更大，因为即使它支付的成本与标记的活动集和清除的整个堆或死集成正比。当您添加卡片标记和其他优化等时，实际垃圾收集器的最坏情况成本实际上可能会更糟，为某些使用模式拾取额外的对数因子。

因此，如果您分配一个大哈希表，即使您在其生命周期内使用 O(1) 搜索来访问它，如果您在垃圾收集环境中这样做，垃圾收集器偶尔也会遍历整个数组，因为它大小为 O(n)，您将在收集期间定期支付该费用。

我们通常将其排​​除在算法复杂性分析之外的原因是垃圾收集以非平凡的方式与您的算法交互。成本有多糟糕在很大程度上取决于您在同一过程中还做了什么，因此分析不是组合的。

此外，除了复制 vs. 紧凑 vs. 标记和扫描问题之外，实现细节会极大地影响由此产生的复杂性：

  1. 跟踪脏位等的增量垃圾收集器几乎可以使那些较大的重新遍历消失。
  2. 这取决于您的 GC 是根据挂钟时间定期工作还是与分配数量成比例地运行。
  3. 标记和扫描风格的算法是并发的还是停止世界的
  4. 是否将新分配标记为黑色，如果它让它们保持白色，直到将它们放入黑色容器中。
  5. 你的语言是否允许修改指针可以让一些垃圾收集器一次性工作。

最后，在讨论算法时，我们正在讨论稻草人。渐近线永远不会完全包含您环境的所有变量。您很少按照设计实现数据结构的每个细节。您在这里和那里借用一个功能，因为您需要快速无序键访问，所以您删除了一个哈希表，您使用联合查找对不相交集进行路径压缩和按等级联合来合并那里的内存区域，因为您不能当您合并区域或您拥有的区域时，您可以支付与区域大小成正比的成本。这些结构被认为是原语，并且在规划“大型”结构的整体性能特征时，渐近线可以帮助您，但了解常量的含义也很重要。

您可以实现具有完美 O(1) 渐近特征的哈希表，只是不要使用垃圾收集；将其从文件映射到内存并自行管理。不过，您可能不喜欢所涉及的常量。

于 2008-12-02T14:44:23.763 回答
0

我认为当许多人抛出“O(1)”这个词时，他们隐含地想到了一个“小”常数，无论“小”在他们的上下文中意味着什么。

您必须根据上下文和常识来进行所有这些大 O 分析。它可能是一个非常有用的工具，也可能是荒谬的，这取决于你如何使用它。

于 2008-12-02T03:38:13.373 回答