题

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

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

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

虽然我之前已经注意到这一点，但一个例子刚刚出现在 Pandincus 问题，“在 C# .NET 中用于在 O(1) 时间内获取项目的‘正确’集合？”.

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

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

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

问题：所有这些准备实际上都是为了一个问题。O(1) 的随意性是什么？为什么它被如此盲目地接受？是否认识到即使 O(1) 也可能大得令人不快，尽管接近常数？或者 O(1) 只是计算复杂性概念对非正式使用的挪用？我很困惑。

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

有帮助吗？

解决方案

我理解的是O（1）不必是恒定的;相反，它是不依赖于所考虑的变量。因此，一个散列查询，可以说（1）相对于在哈希元素的数目为O，但不相对于该数据的长度中的散列被散列或元件比桶。

混乱的另一因素是，大O符号描述限制行为。因此，函数f（N）对于N小的值可能确实表现出极大的变化，但你仍然是正确的说是O（1）如果如N接近无穷大的限制为相对于N个常数。

其他提示

但问题是，人们用术语真的马虎。有3级重要的，但不同的类别这里：

O（1）的最坏情况

这是简单的 - 所有的操作在所有情况下不采取任何比的时间以恒定信息量以下在最坏情况下，因此。访问数组的一个元素被O(1)最坏情况。

O（1）摊销最坏情况

摊销意味着不是每个操作是在最坏情况下O(1)，但对于N操作的任何序列，该序列的总费用是在最坏的情况下无O(N)。这意味着，即使我们不能用一个恒定的约束任何单一的操作成本，总是会有足够“快”操作，以弥补“慢”操作，使得操作的顺序的运行时间是线性的在操作的数量。

例如，标准动态阵列其中，当它充满需要O(1)摊销加倍其容量时间到末插入一个元素，即使有些插入需要O(N)时间 - 总有足够O(1)插入，其插入N项总是需要O(N)时间总

O（1）平均情况

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

。

有关与固定输入随机化算法，我们可以计算出平均情况通过分析算法以及确定所有可能的运行时间的概率分布和取平均值超过该分配（取决于算法的运行时间对于任何给定的输入，这可能是或可能不是可能的，因为停机问题）。

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

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

花点时间让最后一点水槽中 - 为哈希表的O(1)平均情况下的性能来源于假设所有的散列值是均匀分布的。如果这个假设是违反了（它通常不是，但它肯定能够而且确实发生），运行时间不再O(1)平均。

请参阅也拒绝由算法复杂。在本文中，作者讨论他们如何利用在使用Perl中的两个版本，以产生大量与哈希冲突串的默认散列函数的一些弱点。与该字符串列表的武装，他们喂养它们这些字符串，导致由Web服务器使用的哈希表最坏的情况O(N)行为产生一些网络服务器进行拒绝服务攻击。

  

O（1）是指恒定时间和（通常）固定空间

只是为了澄清这些是两个单独的语句。可以在时间具有O（1）但为O（n）的空间或任何

  

时它认识到，即使O（1）可以是不期望的大，即使接近恒定？

O（1）可以是不切实际HUGE和它仍然O（1）。这往往被忽视，如果你知道你有一个非常小的数据集不变的是比复杂更重要的，而对于相当小的数据集，这是两者的平衡。为O（n！）算法可以出执行O（1）如果所述数据集的常量和尺寸是适当的规模。

O（）表示法是复杂的量度 - 而不是时间的算法将采取，或纯度量如何“好”的给定算法是对于给定的目的

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

  • 哈希函数设计合理，避免大量碰撞。
  • 这组密钥几乎是随机分布的，或者至少不是故意设计的，以使哈希函数表现不佳。

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

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

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

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

有一个 警告, ， 然而。也就是说，随着哈希表变得越来越满，将会有 哈希冲突 其中哈希函数将返回数组中已被占用的元素。这将需要一个 碰撞解决 为了找到另一个空元素。

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

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

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

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

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

这 key 将用于确定数组的一个元素来存储 (key, value） 一对。为了确定该元素， hash_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) 时间内执行。

类似地，搜索元素也使用哈希函数。

如果我们想查找密钥 "Name", ，我们将执行 hash_function("Name") 找出所需值位于数组中的哪个元素。

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

一切都很好。让我们尝试添加一个额外的条目 ("Pet", "Dog"). 。然而，有一个问题，如 hash_function("Pet") 回报 18, ，这与 "Name" 钥匙。

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

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

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

当我们尝试搜索时也会出现这个问题 "Pet" 键，试图找到包含 "Pet" 通过执行关键 hash_function("Pet") 最初总是返回 18。

一旦我们查找第 18 个元素，我们就会找到密钥 "Name" 而不是 "Pet". 。当我们发现这种不一致时，我们需要解决冲突，以便检索包含实际内容的正确元素 "Pet" 钥匙。解决哈希冲突是一项附加操作，它使哈希表无法在 O(1) 时间内执行。

我不能给你见过的其他讨论发言，但是存在的至少一个散列算法是的保证是O（1）。

杜鹃散列保持不变，以便有在哈希表中没有链接。插入摊销O（1），检索总是O（1）。我从来没有见过它的一个实现，它的东西，当我在大学里是新发现的。为相对静态的数据集，它应该是一个很好的O（1），因为它计算两个散列函数，执行两个查找，并立即知道答案。

注意，这是假设散列测算是O（1）为好。你可以说，对于长度为K的字符串，任何散列微创O（K）。在现实中，可以结合ķ很容易地，说ķ<1000 O（K）〜= O（1）对于K <1000

有可能是一个概念上的错误，以你是如何理解大哦符号。它的意思是，给定的算法和输入数据集，所述上界算法的运行时间取决于O形函数的值时的数据集的大小趋向于无穷大。

当一个说，算法需要O（n）的时间，这意味着，对于一个算法的最坏的情况下运行时线性地依赖于输入设定的大小。

当的算法花费O（1）时间，这意味着唯一的是，给定的函数T（F），其计算的函数f（n）的，存在一个自然正数k，使得运行时Ť （F）

现在，不以任何方式限制是小的意思，只是它是独立的输入设置的大小。所以，如果我人为限定界K中的数据集的大小，那么它的复杂性将是O（k）的== O（1）。

例如，搜索链接列表上的值的一个实例是O（n）的操作。但是，如果我说一个列表具有至多8个元素，然后为O（n）变为O（8）变为O（1）。

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

有关的哈希表，只要你假设散列函数是好的（无规分布），并充分地稀疏，以便最小化碰撞，以及当所述数据结构是足够致密的，进行再散列，则可以确实认为这是一种O（1）访问时间结构。

在最后，O（1）时间可以被高估了很多事情。对于大的数据结构的一个适当的散列函数的复杂性可能不是微不足道的，并且存在足够的角的情况下的冲突量导致它表现得像一个O（n）的数据结构，并且重散列可能变得昂贵。在这种情况下，像AVL或一个B-tree的O（日志（n））的结构可以是一种更好的选择。

在一般情况下，我认为人们比较使用它们，而不考虑正确性。例如，基于散列的数据结构是O（1）（平均）查如果设计得好，你有一个很好的哈希值。如果一切散列到一个桶，那么它的O（N）。一般情况下，虽然一个使用一个好的算法和密钥分布合理，因此很方便谈论它为O（1）没有所有的资格。同样用表，树等，我们心里有一定的实现和它只是更方便地谈论他们，泛泛讨论时，没有资格。如果，在另一方面，我们正在讨论的具体实现，那么它很可能付出更精确。

哈希表看起来起坐是O（1）相对于表中的项目数，因为无论你有多少条目添加到列表中散列单个项目的成本几乎是一样的，并创建哈希会告诉你该项目的地址。

要回答为什么，这是相关的：在OP被问及为什么O（1）显得那么漫不经心，当在他的脑海它显然不可能在许多情况下适用于被抛向四周。此答案解释了O（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)。

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

O（1）是指，准确地说，该算法的时间复杂性是由一个固定的值限定。这并不意味着它是恒定的，只知道它是不管输入值的界定。严格地说，许多据称O（1）时间的算法实际上没有O（1），只是走得这么慢，他们是有界的所有实际的输入值。

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

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

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

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

此外，超越复制与复制。紧凑型与紧凑型标记和清除问题，实现细节会极大地影响最终的复杂性：

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

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

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

我认为，当很多人到处乱扔的术语“O（1）”他们含蓄心中有一个“小”不断，无论“小”是指在其背景下。

您必须采取所有背景和常识这个大O分析。它可以是一个非常有用的工具，也可以是可笑的，这取决于你如何使用它。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top