O（log N）== O（1） – 为什么不呢？
每当我考虑algorithm/数据结构，我倾向于用常量来replacelog（N）部分。 哦，我知道日志（N）分歧 – 但在真实世界的应用程序中是否重要？
日志（无穷远）<100为实际目的。
我真的很好奇现实世界的例子，这不成立。
澄清：
- 我明白O（f（N））
- 我很好奇真实世界的例子， 渐近行为比实际performance的常量更重要。
- 如果log（N）可以被一个常量替代，它仍然可以用O（N log N）中的一个常量代替。
这个问题是为了（a）娱乐和（b）收集争论的使用，如果我再次（关于devise的performance）的争议。
我认为这是一个务实的方法; O（logN）永远不会超过64.在实践中，只要术语和O（logN）一样小，就必须测量常量因素是否胜出。 也可以看看
阿克曼function的用途？
引用自己对另一个答案的评论：
[大哦]'分析'只是至lessO（N）的因素。 对于任何较小的因素，大哦分析是无用的，你必须测量。
和
“用O（logN）你的input大小确实重要。” 这是问题的全部。 当然这在理论上很重要。 OP要求的问题是， 在实践中是否重要？ 我认为答案是否定的，没有，也不会有数据集logN将会增长得如此之快以至于总是被打上一个恒定时间的algorithm。 即使对于我们孙子孙辈中可以想象的最大的实际数据集，logNalgorithm也有一个很好的机会来打败一个恒定的时间algorithm – 你必须经常测量。
编辑
一个好的谈话：
http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey
在一半左右，Rich讨论了Clojure的散列尝试，显然是O（logN），但是对数的基数很大，因此即使它包含了40亿个值，trie的深度也是至多6。 这里“6”仍然是一个O（logN）值，但它是一个非常小的值，所以select放弃这个可怕的数据结构，因为“我真的需要O（1）”是一个愚蠢的事情。 这强调了这个问题的大多数其他答案如何从实用主义者的angular度来看是错误的 ，他们希望他们的algorithm“跑得快”和“规模好”，而不pipe“理论”是什么。
编辑
也可以看看
http://queue.acm.org/detail.cfm?id=1814327
这说
如果这些操作导致页面错误和磁盘操作缓慢，那么O（log2（n））algorithm有什么好处呢？ 对于大多数相关的数据集，O（n）甚至O（n ^ 2）algorithm（避免页面错误）将围绕它运行圆圈。
（但请阅读文章的上下文）。
大O符号告诉你如何随着input的增加你的algorithm的变化。 O（1）告诉你input增长多less并不重要，algorithm总是一样快。 O（logn）表示algorithm会很快，但是随着input的增长，需要更长的时间。
O（1）和O（logn）在开始合并algorithm时有很大的不同。
例如，以索引进行连接。 如果你可以在O（1）而不是O（logn）中进行连接，你将会获得巨大的性能提升。 例如对于O（1）你可以join任何次数，你仍然有O（1）。 但是对于O（logn），您需要每次将操作计数乘以logn。
对于大的input，如果你的algorithm已经是O（n ^ 2），那么你宁愿做一个内部为O（1）的操作，而不是内部的O（logn）。
还要记住，任何东西都可以有一个不变的开销。 假设不断的开销是100万。 对于O（1），恒定的开销不会像O（logn）一样放大操作的数量。
还有一点就是，大家都认为O（logn）代表了树形数据结构中的n个元素。 但它可能是任何东西，包括文件中的字节。
这是一个常见的错误 – 记住大O符号不会告诉你一个algorithm在给定值的绝对性能，它只是告诉你一个algorithm的行为，因为你增加了input的大小。
当你把它放在这个上下文中时，为什么algorithmA〜O（logN）和algorithmB〜O（1）algorithm是不同的：
如果我在大小为a的input上运行A，那么在大小为1000000 * a的input上，我可以预期第二次input只要第一次input就会logging（1,000,000）次
如果我在大小为a的input上运行B，那么在大小为1000000 * a的input上，我可以预期第二个input的时间与第一个input大约相同
编辑 ：思考你的问题多一些，我认为有一些智慧在里面。 虽然我不会说O（lgN）== O（1）是正确的，但是O（lgN）algorithm可能会用于O（1）algorithm。 这又回到了上面的绝对性能上：只知道一个algorithm是O（1），而另一个algorithm是O（lgN）不足以宣告你应该使用O（l）到O（lgN），这当然O（lgN）可能为您提供最好的服务。
你要求一个真实的例子。 我会给你一个。 计算生物学。 用ASCII编码的一串DNA在空间上是千兆字节级的。 一个典型的数据库显然会有成千上万的这样的股票。
现在，在索引/searchalgorithm的情况下，log（n）倍数与常量耦合时会产生很大的差异。 之所以？ 这是您的input大小是天文数字的应用之一。 另外，input大小将一直持续增长。
无可否认，这类问题很less见。 只有这么多的应用程序这么大。 在这样的情况下，虽然…它造成了一个不同的世界。
平等，你描述的方式，是一种常见的符号滥用。
澄清：我们通常写f（x）= O（logN）暗示“f（x）是O（logN）”。
无论如何， O(1)意味着执行一个动作的步数/时间（作为上限）是固定的，而不pipeinput集有多大。 但是，对于O(logN) ，步数/时间仍然随着input大小（其对数）的增长而增长，它只是增长非常缓慢。 对于大多数真实世界的应用程序，假设这个步骤数不会超过100，那么可能是安全的。但是我敢打赌，有多个数据集的例子足以将您的语句标记为危险和无效（数据包跟踪，环境测量和还有很多）。
对于足够小的N，O（N ^ N）实际上可以被replace为1.不是O（1）（根据定义），但对于N = 2，可以将它看作一个具有4个部分的操作，或者是一个恒定时间操作。
如果所有的操作需要1小时呢？ O（logN）和O（1）之间的差异很大，即使是小的N.
或者如果你需要运行一千万次的algorithm？ 好吧，那花了30分钟，所以当我在一个数据集上运行一百倍的数据时，它仍然需要30分钟，因为O（logN）与O（1）是一样的……呃…什么？
你的陈述“我明白O（f（N））”显然是错误的。
真实世界的应用程序，哦…我不知道… O（）的每个使用 – 符号EVER？
二进制search例如在1000万个项目的sorting列表中。 当数据变得足够大时，我们使用哈希表的原因就是这个原因。 如果你认为O（logN）和O（1）是一样的，那你为什么要用一个散列而不是二叉树呢？
正如很多人已经说过的，对于现实世界，在考虑O（log N）的因素之前，首先需要考虑常量因素。
然后，考虑你会期望N是什么。 如果你有充分的理由认为N <10，你可以使用线性search而不是二进制。 这是O（N），而不是O（log N），根据你的灯光将是重要的 – 但一个线性search移动到前面的元素可能会胜过一个更复杂的平衡树， 取决于应用程序 。
另一方面，请注意，即使log N不可能超过50，性能因子10也是非常巨大的 – 如果您是计算受限的，那么这样的因素很容易造成或破坏您的应用程序。 如果这还不够，你会在algorithm中经常看到（log N）^ 2或（logN）^ 3的因子，所以即使你认为你可以忽略一个因子（log N），那也不意味着你可以忽略更多。
最后，请注意，线性规划的单纯形algorithm的最坏情况性能为O（2 ^ n）。 但是，对于实际问题，最糟糕的情况永远不会出现; 在实践中，单纯形法algorithm快速，相对简单，因此非常受欢迎。
大约30年前，有人开发了一个线性规划的多项式时间algorithm，但是由于结果太慢 ，所以并不实用。
目前，对于线性规划（具有多项式时间的情况，为了什么是值得的），存在实用的替代algorithm，其在实践中可以优于单纯形法。 但是，依靠这个问题，单纯形法还是有竞争力的。
O(log n)通常与O(1)不可区分的观察结果是好的。
作为一个熟悉的例子，假设我们想要在一个1,000,000,000,000个元素的有序数组中find一个元素：
- 采用线性search，search平均需要500亿步
- 使用二分search，search平均需要40步
假设我们向正在search的数组添加了一个元素，现在我们必须search另一个元素：
- 采用线性search，search平均需要500,000,000,001步（难以区分的变化）
- 与二进制search，search平均40步骤（难以区分的变化）
假设我们将要search的数组的元素数加倍，现在我们必须search另一个元素：
- 采用线性search，search平均需要1,000亿步（非常明显的变化）
- 使用二分search，search平均需要41个步骤（难以区分的变化）
从这个例子我们可以看出，对于所有的意图和目的，像二进制search这样的O(log n)algorithm通常与O(1)algorithm无法区分，就像全知。
接下来的一点是：*我们使用O(log n)algorithm，因为它们常常与常量时间不可区分，并且因为它们通常执行比线性时间algorithm更好的性能。
显然，这些例子假定合理的常数。 显然，这些是一般性的观察，并不适用于所有情况。 显然，这些点适用于曲线的渐近端，而不是n=3端。
但是这个观察解释了为什么，例如，我们使用诸如调整查询来执行索引查找而不是表扫描的技术 – 因为索引查找在几乎恒定的时间内运行，不pipe数据集的大小如何，而表扫描是在足够大的数据集上速度很慢。 索引查找是O(log n) 。
您可能会对Soft-O感兴趣，而忽略对数成本。 在维基百科检查这一段 。
这个“重要”是什么意思？
如果你面对O(1)algorithm和O(lg n)algorithm的select，那么你不应该假设它们是相等的。 你应该select恒定的时间。 你为什么不呢？
如果不存在恒定时间algorithm，那么对数时间algorithm通常是最好的。 再次，它是否重要 ？ 你只需要采取最快的，你可以find。
你可以给我一个情况，你可以通过定义两个平等获得任何东西吗？ 最好的情况是没有什么区别，最糟糕的是，你会隐藏一些真正的可扩展性特征。 因为通常，恒定时间algorithm将比对数algorithm快。
就像你所说的，即使lg(n) < 100为所有的实际目的，这仍然是你的其他开销之上的一个因子100。 如果我调用你的函数N次，那么它开始关心你的函数是对数时间还是常量，因为总的复杂度是O(n lg n)或者O(n) 。
所以，不要问在“现实世界”中，假定对数的复杂性是否“恒定”，是否有任何意义。
通常你可以假定对数algorithm足够快 ，但是通过考虑它们常数你会得到什么？
O（logN）* O（logN）* O（logN）是非常不同的。 O（1）* O（1）* O（1）仍然是恒定的。 另外一个简单的快排风格O（nlogn）不同于O（n O（1））= O（n）。 尝试sorting1000和1000000元素。 由于log（n ^ 2）= 2log（n），后者不是1000倍，而是2000倍，
这个问题的标题是误导性的（select鼓吹辩论，介意你）。
O（log N）== O（1）显然是错误的（海报知道这一点）。 大O符号，根据定义，是渐近分析。 当你看到O（N）时，N被接近无穷大。 如果N被分配一个常量，那不是大O.
请注意，这不仅仅是一个只有理论计算机科学家需要关心的细节。 所有用来确定algorithm的O函数的algorithm都依赖于它。 当您为algorithm发布O函数时，您可能会忽略大量有关其性能的信息。
大O分析是很酷的，因为它可以让你比较algorithm而不会陷入特定于平台的问题（字大小，每个操作的指令，内存速度与磁盘速度）之间。 当N走向无限时，这些问题就消失了。 但是，当N是10000,1000,100时，那些问题以及我们在O函数中所遗留的所有其他常数开始变得很重要。
为了回答海报的问题：O（log N）！= O（1），你说得对，有O（1）的algorithm有时候比O（log N）的algorithm要好得多，的input，以及在大O分析过程中忽略的所有内部常量。
如果你知道你将要启动N，那么使用Big O分析。 如果你不是，那么你需要一些经验testing。
理论上
是的，在实际情况下，log（n）以常数为界，我们将说100。但是，在正确的情况下将log（n）replace为100仍然会丢弃信息，从而使得操作的上限计算松散，用处不大。 在您的分析中用O（1）代替O（log（n））可能会导致您的大n案件的执行比您预期的小n案件差100倍。 你的理论分析可能会更准确，并可能在你build立系统之前预测到一个问题。
我认为，大O分析的实际目的是尽可能早地尝试和预测algorithm的执行时间。 您可以通过删除log（n）项来简化分析过程，但是却降低了估计的预测能力。
在实践中
如果您阅读Larry Page和Sergey Brin在Google架构上的原始文章，他们会讨论如何使用哈希表来确保查找caching的网页只需要一次硬盘查找。 如果您使用B树索引来查找，则可能需要四到五个硬盘search才能执行未caching查找[*]。 在caching的网页存储中，将磁盘需求翻两番，从业务angular度来看是值得关注的，而且如果不排除所有O（log（n））条款，则可以预测。
PS抱歉，以谷歌为例，他们就像戈德温法则的计算机科学版中的希特勒一样。
[*]假设从磁盘读取4KB，索引中有1000亿个网页，B-树节点中每个键约16个字节。
正如其他人所指出的，Big-O告诉你如何衡量你的问题的performance。 相信我 – 这很重要。 我遇到过几次algorithm，因为速度太慢，所以算是很糟糕，不能满足客户的需求。 了解差异并找出一个O（1）解决scheme是一个巨大的改进很多次。
但是，当然这并不是全部，例如，您可能会注意到，由于两个algorithm在小数据集上的行为，快速sortingalgorithm总是会切换到小元素的插入sorting（Wikipedia说8-20）。
所以这是一个理解你将要做什么权衡的问题，这个问题包括对问题，体系结构和经验的全面理解，以便理解使用哪个以及如何调整所涉及的常量。
没有人说O（1）总是比O（log N）好。 但是，我可以保证，O（1）algorithm也可以更好地扩展，因此，即使对系统中有多less用户或要处理的数据大小做出错误的假设，也无所谓到algorithm。
是的，log（N）<100为最实际的目的，并且不，你不能总是取代它。
例如，这可能会导致估计程序性能的严重错误。 如果O（N）程序在1ms内处理了1000个元素的数组，那么你确定它会在1秒钟左右处理10 6个元素。 如果程序是O（N * logN），那么处理10 6个元素需要2秒。 这种差异可能是至关重要的 – 例如，您可能认为您拥有足够的服务器function，因为您每小时获得3000个请求，并且您认为您的服务器最多可以处理3600个请求。
另一个例子。 假设你有函数f（）在O（logN）中工作，并且在每个迭代中调用函数g（），它也在O（logN）中工作。 然后，如果你用常量replace两个日志，你认为你的程序工作在一个固定的时间。 现实将是残酷的 – 两个日志可能会给你100 * 100乘法器。
当你不确定O（log n）= O（1）时，确定Big-O符号的规则更简单。
正如krzysio所说，你可能会积累O（log n）s，然后他们会产生非常明显的差异。 想象一下你做一个二分search：O（log n）比较，然后想象每个比较的复杂度O（log n）。 如果你忽略了两者，你会得到O（1）而不是O（log 2 n）。 同样，你可能会以某种方式到达O（log 10 n），然后你会注意到不是太大的“n”有很大的差别。
假设在整个应用程序中，一个algorithm占用户等待最常见操作的时间的90％。
假设O（1）操作在你的体系结构上花费了一秒钟，O（logN）操作基本上是0.5秒* log（N）。 那么，在这一点上，我真的很想在曲线和线的交点处画一个箭头的图表，说：“这里很重要。 在这种情况下，您想使用小数据集的log（N）op和大数据集的O（1）op。
大O符号和性能优化是一个学术性的练习，而不是为用户提供已经便宜的操作的实际价值，但是如果在关键path上的操作是昂贵的，那么你打赌很重要！
对于任何可以input不同大小的input的algorithm，它所需要的操作次数是由某个函数f（N）所上界的。
所有的大O都告诉你这个函数的形状。
-
O（1）表示存在一些数字A，使得f（N）<A表示大N.
-
O（N）表示存在一些使得f（N）<AN的大N.
-
O（N ^ 2）表示存在某个A，使得对于大的N，f（N）<AN ^ 2。
-
O（log（N））意味着存在一些使得f（N）<AlogN为大N.
大O没有提到A有多大（即algorithm有多快），或者这些function相互交叉。 它只是说当你比较两种algorithm时，如果他们的big-os不同，那么有一个N值（可能很小或者可能很大），其中一个algorithm将开始超越另一个algorithm。
你是对的，在很多情况下，这对于实践来说并不重要。 但关键的问题是“多快GROWS N”。 我们所知道的大部分algorithm都是以input的大小来进行的，因此线性增长。
但有些algorithm复杂地导出了N的值。 如果N是“有X个不同数字的彩票可能的彩票组合数量”，那么你的algorithm是O（1）还是O（logN）
大OH告诉你，一个algorithm是比另一个给定的一个恒定的因素更快。 如果你的input意味着一个足够小的常数因子，你可以通过线性search而不是对某个基的log（n）search来看到很好的性能收益。
O（log N）可能会引起误解。 以红黑树上的操作为例。
操作是O（logN），但相当复杂，这意味着许多低级操作。
我不相信algorithm，你可以自由selectO（1）与一个大的常量和O（logN）真的存在。 如果在开始的时候有N个元素可以使用，那么使它成为O（1）显然是不可能的，唯一可能的是将N移到代码的其他部分。
我想说的是，在所有的实际情况下，我知道你有一些空间/时间的折衷，或者一些预处理，比如把数据编译成更高效的forms。
也就是说，你不是真的走O（1），你只是把N部分移到其他地方。 要么你用一些内存量来交换你的代码的某个部分的性能，要么用另一个交换你的algorithm的一部分的性能。 为了保持理智，你应该总是看大图。
我的意思是，如果你有N件物品，他们不能消失。 换句话说，你可以select低效的O（n ^ 2）algorithm或者更差的O（n.logN）：这是一个真正的select。 但你永远不会去O（1）。
我试图指出的是，对于每个问题和初始数据状态，都有一个“最佳”algorithm。 你可以做得更糟，但永远不会更好。 有了一些经验，你可以很好地猜测这种复杂性是什么。 那么如果你的整体治疗符合这个复杂性，你就知道你有什么 您将无法降低复杂性，但只能移动它。
如果问题是O（n），它不会变成O（logN）或O（1），那么只需要添加一些预处理，使整体复杂性不变或更糟，并且可能稍后的步骤将得到改进。 假设你想要一个数组的较小的元素，你可以在O（N）中进行search，或者使用任何常见的O（NLogN）sorting处理对数组进行sorting，然后使用O（1）进行sorting。
随便那么做是个好主意？ 只有当你的问题也问第二，第三等元素。 那么你最初的问题确实是O（NLogN），而不是O（N）。
如果你等待十倍或二十倍的时间，结果就不一样了，因为你简化了O（1）= O（LogN）。
我正在等待一个反例;-)这是任何真正的情况下，你有O（1）和O（LogN）之间的select，每个O（LogN）的步骤将不会比较O（1）。 你所能做的只是采取一种更糟糕的algorithm，而不是自然的algorithm，或者将一些重大的处理移动到较大图片的其他部分（预计算结果，使用存储空间等）
假设您使用在O（logN）中运行的image processingalgorithm，其中N是图像的数量。 现在……说定时运行会让人相信不pipe有多less图像，它仍然会在相同的时间内完成它的任务。 如果在单个图像上运行该algorithm将假设需要一整天，并假设O（logN）永远不会超过100 …想象一下，那个人的惊喜，试图在一个非常大的图像数据库上运行该algorithm – 他希望能在一天左右的时间内完成……但是这需要几个月的时间才能完成。
