我已经注意到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)的习惯,我已经修复了.我仍然在寻找好的答案,在一些情况下,一些评论主题比他们的答案更有趣.