我已经注意到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)的习惯,我已经修复了.我仍然在寻找好的答案,在一些情况下,一些评论主题比他们的答案更有趣.
问题是人们对术语非常邋..这里有3个重要但不同的类:
这很简单 - 在最坏的情况下,所有操作只需要一个恒定的时间,因此在所有情况下都是如此.访问数组的元素是O(1)最糟糕的情况.
摊销意味着并非每个操作都O(1)处于最坏的情况,但对于N个操作的任何序列,序列的总成本O(N)在最坏的情况下是否定的.这意味着即使我们不能通过常量限制任何单个操作的成本,总会有足够的"快速"操作来弥补"慢"操作,使得操作序列的运行时间是线性的在运营数量上.
例如,标准动态数组在填满时将其容量加倍需要O(1)在末尾插入元素的分摊时间,即使某些插入需要O(N)时间 - 总是有足够的O(1)插入插入N个项目总是需要O(N)时间总计.
这个是最棘手的.平均情况有两种可能的定义:一种用于具有固定输入的随机算法,一种用于具有随机输入的确定性算法.
对于具有固定输入的随机算法,我们可以通过分析算法并确定所有可能的运行时间的概率分布并计算该分布的平均值来计算任何给定输入的平均情况运行时间(取决于算法,这可能或由于停机问题,可能无法实现.
在另一种情况下,我们需要输入的概率分布.例如,如果我们要测量排序算法,那么一个这样的概率分布将是具有全N的分布!输入的可能排列同样可能.然后,平均情况运行时间是所有可能输入的平均运行时间,由每个输入的概率加权.
由于这个问题的主题是确定性的哈希表,我将重点关注平均情况的第二个定义.现在,我们不能总是确定输入的概率分布,因为我们可以对任何事物进行散列,这些项可能来自用户在文件系统中输入或从文件系统中输入.因此,在谈论散列表时,大多数人只是假设输入表现良好并且散列函数表现良好,使得任何输入的散列值基本上在可能的散列值的范围内均匀地随机分布.
花点时间让最后一点陷入其中 - O(1)哈希表的平均情况表现来自假设所有哈希值均匀分布.如果违反了这个假设(通常不是这样,但它确实可以而且确实发生),运行时间不再O(1)平均.
另请参阅算法复杂性拒绝服务.在本文中,作者讨论了他们如何利用两个Perl版本使用的默认哈希函数中的一些弱点来生成大量具有哈希冲突的字符串.有了这个字符串列表,他们通过向这些字符串提供这些字符串,导致O(N)Web服务器使用的哈希表中的最坏情况行为,对某些Web服务器产生了拒绝服务攻击.
我的理解是O(1)不一定是恒定的; 相反,它不依赖于所考虑的变量.因此,关于散列中的元素的数量,散列查找可以说是O(1),而不是关于散列的数据的长度或散列中的元素与桶的比率.
困惑的另一个原因是大O符号描述了限制行为.因此,对于小N值的函数f(N)可能确实显示出很大的变化,但是如果N接近无穷大的极限相对于N是恒定的,那么你仍然可以说它是O(1).
O(1)表示恒定时间和(通常)固定空间
只是为了澄清这些是两个单独的陈述.你可以在时间上有O(1)但在空间或其他方面有O(n).
是否认识到即使O(1)可能不合需要地大,即使接近常数？
O(1)可能是不切实际的巨大的,它仍然是O(1).经常被忽略的是,如果你知道你将拥有一个非常小的数据集,那么常数比复杂性更重要,对于相当小的数据集,它是两者之间的平衡.如果数据集的常数和大小具有适当的比例,则O(n!)算法可以胜过O(1).
O()表示法是复杂性的度量 - 不是算法将采用的时间,或者是给定算法对于给定目的"好"的纯度度量.
我可以看到你在说什么,但我认为哈希表中的查找具有O(1)的复杂性的声明存在一些基本假设.
散列函数设计合理,可避免大量冲突.
这组密钥几乎是随机分布的,或者至少不是故意设计的,以使散列函数表现不佳.
哈希表查找的最坏情况复杂度是O(n),但鉴于上述2个假设,这种情况极不可能.
Hashtables是一种支持O(1)搜索和插入的数据结构.
哈希表通常具有键和值对,其中键用作函数的参数(哈希函数),该函数将确定值在其内部数据结构(通常是数组)中的位置.
由于插入和搜索仅取决于散列函数的结果,而不取决于散列表的大小和存储的元素数量,因此散列表具有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",我们将执行a 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)时间内不执行.
京公网安备 11010802040832号 | 京ICP备19059560号-6 