每当我考虑算法/数据结构我倾向于由常量替换日志（N）的部分。 哦，我知道的log（n）发散 - 但它在现实世界的应用有关系吗？
日志（无穷大）<100对于所有的实际目的。
我对现实世界的例子，其中这并不持有真的很好奇。
澄清：
- 我明白O（F（N））
- 我好奇的现实世界的例子，其中渐近行为更重要比实际性能的常数 。
- 如果log（N）可以用一常数来代替它仍可以通过一个常数替换为O（N日志N）。
这个问题是（一）娱乐和（b）的缘故，收集论据，如果我（再次）碰上一个关于设计的性能争论使用。
Answer 1:
我认为这是一个务实的做法; O（logn）时间将不会超过64。在实践中，只要条件得到尽可能“小”为O（logN）的，你必须衡量是否恒定因素胜出。 也可以看看
阿克曼函数的使用？
为了从另一个答案评论引用自己：
[大哦]“分析”为至少O（N）仅因素事项。 对于任何较小的因素，大哦分析是无用的，你必须衡量。
和
“随着O（logN）的输入您的大小很重要。” 这是问题的关键所在。 当然，它的事项...... 在理论上 。 在OP问的问题是，它在实践中重要吗？ 我争辩说，答案是否定的，没有，也永远不会是一个数据集用于其将logN个这么快增长，因为总是被打的恒定时间算法。 即使是最大的实际数据集在我们的孙辈的寿命可以想象，一个算法logN个跳动具有一定的时间算法的一个公平的机会 - 你必须经常测量。
编辑
相谈甚欢：
http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey
约一半，丰富讨论Clojure的散列尝试，这显然是O（logN）的，但对数的底数大，所以特里树的深度最多为6，即使它包含4个十亿值。 这里的“6”仍然是一个O（logN）的值，但它是一个令人难以置信的小值，所以选择，因为“我真的需要O（1）”是做愚蠢的事丢弃这个真棒数据结构。 这强调了其他大部分回答这个问题的是如何简单地从谁希望自己的算法，“跑得快”和“很好地扩展”，不管是什么“理论”说实用主义者的观点是错误的 。
编辑
也可以看看
http://queue.acm.org/detail.cfm?id=1814327
它说
有什么好处是O（LOG 2（n））的算法，如果这些行动导致页面错误和缓慢的磁盘操作？ 对于大多数数据集相关的O（N），甚至为O（n ^ 2）算法，避免了缺页，将运行它周围的圈子。
（但去阅读文章的上下文）。
Answer 2:
大O符号告诉你你的算法不断增长的输入如何变化。 O（1）告诉你这不要紧，你输入多少增长，该算法将永远是一样快。 O（LOGN）说，该算法将是快，但作为输入的增长，将需要更长的时间。
O（1）和O（LOGN）会产生很大的性差异，当你开始算法结合起来。
以具有例如索引做连接。 如果你能做到在O连接（1）而不是O（LOGN）你将有巨大的性能提升。 例如用O（1）你可以加入的任何时间量，你仍然有O（1）。 但与O（LOGN），你需要通过每次LOGN乘以操作计数。
对于大的投入，如果你有一个算法，这是为O（n ^ 2）已经，你更愿意做的是O（1）内，而不是O（LOGN）内的操作。
还记得任何事情大O可以有一个恒定的开销。 假设恒定的开销为100万。 用O（1），该恒定的开销不放大操作的数量多达O（logn）时间一样。
另一点是，每个人都认为O（logn）时间的表示用于例子的树数据结构的n个元素。 但它可以是任何东西，包括文件的字节。
Answer 3:
这是一个常见的错误 - 记大O符号是不是告诉你关于算法的绝对性能在给定的值，它只是告诉你一个算法的行为，你增加输入的大小。
当你把它在这方面为什么算法A〜O（logn）时间和算法乙〜O（1）算法是不同的很清楚：
如果我大小百万的输入上尺寸的输入运行A，那么* A，I可以期望第二输入采取日志（1,000,000）倍，只要第一输入
如果我大小百万的输入上尺寸的输入运行B，那么* A，I可以期望第二输入取大约相同的时间量作为第一输入
编辑 ：在你的问题的思考多一些，我认为有一些智慧，它可以了。 虽然我绝不会说这是正确的说O（LGN）== O（1），这可能是一个O（LGN）算法可能会超过一个O（1）算法中使用。 这种退约的绝对性能点之上：只要知道一个算法是O（1），另一种算法是O（LGN）是不够的，声明你应该（1）在O（LGN）使用O，它肯定可能给你的可能的输入范围内的O（LGN）可能最好的为您服务。
Answer 4:
你问一个真实的例子。 我给你一个。 计算生物学。 在ASCII编码DNA的一条链上的某处空间千兆字节的水平。 一个典型的数据库会显然有成千上万这样的股。
现在，在一个索引/搜索算法的情况下，该日志（n）的多个使一个大的差异时，与常量耦合。 之所以？ 这是你输入的大小是天文数字的应用之一。 此外，输入大小会一直持续增长。
诚然，这些类型的问题是罕见的。 只有这么多的应用中，这种大。 在这种情况下，虽然...它使一个不同的世界。
Answer 5:
平等，你描述的方式，是符号的一种常见的滥用。
澄清：我们通常写F（X）= O（logN）的暗示 “F（x）是O（logn）时间”。
无论如何， O(1)指的是恒定的步数/时间（作为上界），而不管所述输入集多大执行动作。 但对于O(logN) ，步数/时间仍然增长作为输入的大小（它的对数）的函数，它只是生长速度非常缓慢。 对于大多数现实世界的应用程序，你可能是安全的假设，这个数字的步骤不会超过100，但是我敢打赌有数据集足够大，以纪念你的说法的多个例子既危险又无效（数据包的痕迹，环境测量，并还有很多）。
Answer 6:
对于足够小的N，O（N ^ N）可以在实践中以1不替换为O（1）（根据定义），但对于N = 2可以用4份，或恒定时间把它看作是一个操作操作。
如果所有操作都1小时？ -O之间的差（对数N）和O（1）是再大，即使使用小N.
或者，如果你需要运行算法千万倍？ 好吧，这把30分钟，所以当我在数据集上百倍大的运行它，它仍然应该采取30分钟因为O（logN）的是“相同的”为O（1）......嗯......什么？
你的声明说：“我明白了O（F（N））”显然是假的。
现实世界中的应用，哦...我不知道....邻每次使用（） - 符号EVER？
在10万件，例如排序列表二进制搜索。 这是这个原因，我们使用哈希表时，得到的数据足够大。 如果你觉得O（logN）的相同O（1），那么你怎么可能会使用散列而不是一个二叉树的？
Answer 7:
正如许多人已经表示，对于现实世界中，你需要不断的因素看第一，甚至担心（日志N）O的因素之前。
然后，请考虑您会期待N到是什么。 如果你有充分的理由认为N个<10，你可以用一个线性搜索，而不是一个二进制。 这是O（N），而不是为O（log N），它根据你的灯将显著-但移动的线性搜索找到的元素到前面可能跑赢更复杂的平衡树， 根据不同的应用 。
在另一方面，需要注意的是，即使日志N是不太可能超过50，10性能的因素实在是巨大的 - 如果你是计算密集型，像这样的尺寸可以很容易造就你的应用程序。 如果你没有足够的，你会经常看到^ 2（10即）的（日志N）的因素算法^ 3，因此，即使你认为你可以忽略的（日志N）的一个因素，这并不意味着你可以忽略更多的人。
最后，注意，线性规划的单纯形法为O的最坏情况下的性能（2 ^ N）。 但是，对于实际问题，在最坏的情况下从未出现; 在实践中，单纯形法快，比较简单，因此很受欢迎。
大约30年前，有人开发了线性规划的多项式时间算法，但起初并不实用，因为结果是太慢了 。
如今，有线性规划实用的替代算法（用多项式时间wost情况下，什么是值得），它可以在实践中超越单纯形法。 不过，根据不同的问题，单纯形法是仍然具有竞争力。
Answer 8:
的观察结果O(log n)距离常常难以区分O(1)是一个好的。
作为一个熟悉的例子，假设我们想在一个1,000,000,000,000元素的排序阵列，以找到一个单一的元素：
- 与线性搜索，搜索平均需要5000亿个步骤
- 二进制搜索时，搜索平均需要40步
假设我们添加了一个元素的数组，我们正在寻找，现在我们必须寻找另一种元素：
- 与线性搜索，搜索平均需要500000000001个步骤（不可区分的变化）
- 二进制搜索，搜索平均需要40步（不可区分的变化）
假设我们加倍数组中的元素，我们正在寻找，现在我们必须寻找另一种元素的数量：
- 与线性搜索，搜索平均需要1,000,000,000,000步骤（非常显着的变化）
- 二进制搜索，搜索平均需要41个步骤（不可区分的变化）
正如我们从这个例子可以看出，对于所有意图和目的，一个O(log n)像二进制搜索算法是从经常难以区分O(1)算法一样无所不知。
外卖的观点是：*我们用O(log n)算法，因为他们往往是从固定的时间没有区别，因为他们经常执行惊人比线性时间的算法更好。
显然，这些例子假定合理的常量。 显然，这些都是通用的意见，并不适用于所有情况。 显然，这些点在曲线，而不是的渐近端应用n=3端部。
但这个观察解释了为什么，例如，我们使用这种技术作为调整查询做索引查找，而不是表扫描 - 因为索引查找工作在几乎恒定的时间无论是数据集的大小，而表扫描在足够大的数据集crushingly缓慢。 索引查找是O(log n) 。
Answer 9:
您可能会感兴趣的软O，而忽略对数成本。 检查本款在维基百科。
Answer 10:
你是什么意思它是否“问题”？
如果你面对一个的选择O(1)算法和O(lg n)一个，那么你不应该假设他们是平等的。 你应该选择恒定时间之一。 你为什么不？
如果没有固定时间的算法存在，那么对数时间的一个通常是你可以得到最好的。 再次，它是那么重要吗？ 你只要把你能找到最快的。
你能给我一个情况下，你会通过定义两个作为平等的收获？ 充其量，它会做没有什么区别，而在最坏的情况，你会隐藏一些真正的可扩展性的特点。 因为通常情况下，一个恒定时间算法会比的对数的速度更快。
即使如你所说， lg(n) < 100所有的实际目的，这仍然是一个因素100在您的其他开销上。 如果我打电话给你的函数，N次，然后它开始不管你的函数的运行对数时间或恒定，因为总的复杂性，然后O(n lg n)或O(n)
因此，而不是问“它的问题”你认为对数的复杂性在“现实世界”是恒定的，我会问，如果有这样做的任何一点。
通常你可以假设，对数算法是速度不够快 ，但你是什么考虑他们不断获得什么？
Answer 11:
O（logN）的* O（logN）的* O（logN）的有很大的不同。 O（1）* O（1）* O（1）是静止不变。 也简单快速排序式的O（nlogn）是为O不同（N O（1））= O（N）。 尝试整理1000至1000000元。 后者不是1000倍慢，这是2000倍，因为的log（n ^ 2）= 2log（n）的
Answer 12:
问题的标题有误导之嫌（精心挑选鼓起来辩论，请注意）。
O（日志N）== O（1）显然是错误的（和海报是意识到了这一点）。 大O表示法，顾名思义，对于渐近分析。 当你看到O（N），N取接近无穷大。 如果N被分配一个恒定的，它不是大O.
请注意，这不只是一个吹毛求疵的细节，只是理论计算机科学家需要关心。 所有用于确定的算法O功能的运算依赖于它。 当您发布O功能为你的算法，你可能会忽略了很多关于它的性能信息。
大O分析是冷静，因为它可以让你比较算法，而在平台的具体问题陷入困境（文字大小，每个操作指令，存储器速度与磁盘速度）。 当N趋于无穷大，这些问题就消失了。 但是，当N为10000，1000，100，这些问题的，以及所有我们留出了O功能的其他常量一起，开始无所谓。
要回答海报的问题：为O（log N）= O（1），和你说的没错，带O算法（1）有时并不比带O算法好得多（日志N），根据不同的尺寸！输入，和所有的好大O分析期间忽略的那些内部常量的。
如果你知道你将要手摇N，然后用大O分析。 如果你没有，那么你就需要一些实证检验。
Answer 13:
理论上
是的，在实际情况下的log（n）乘以一个常数界，我们会说100.然而，在它是正确的情况下，100更换的log（n）仍然扔掉的信息，使得上限，你有操作计算松散的和不太有用。 通过在分析一个O（1）更换为O（log（n））的可能会导致您大的n的情况下执行基于你的小样本情况下比你预期的要差100倍。 你的理论分析可能是更准确，可以预测的问题，您会建立系统之前。
我认为，大O分析的实际目的是尽可能早地尝试，并预测你的算法的执行时间。 你可以让你分析划去的log（n）而言更容易，但你已经减少了估计的预测能力。
在实践中
如果你读了谷歌架构原始论文由拉里·佩奇和谢尔盖·布林，他们谈论使用哈希表的一切，以保证如缓存网页的查找只需要一个硬盘求。 如果您使用的B树索引来查找您可能需要四五个硬盘力求做到未缓存查找[*]。 在你的缓存网页存储翻两番的磁盘需求是值得从商业角度关心和可预测的，如果你不赶所有的O（日志（n））的条款。
PS对不起使用谷歌作为一个例子，他们就像希特勒的计算机科学版高德温法则 。
[*]假设4KB从磁盘中读取，1000亿个网页在索引中，每〜键16个字节在B树节点。
Answer 14:
正如其他人所指出的那样，大O告诉你有关你的问题的表现如何扩展。 相信我 - 它很重要。 我也遇到过几次算法是太可怕了，并不能满足客户的需求，因为他们太缓慢。 理解的差异，找到一个O（1）解决方案是很多次了巨大的改进。
但是，当然，这并不是故事的全部 - 例如，您可能会注意到快速排序算法将随时切换到插入排序为小元素（维基百科说8 - 20），因为在小数据集两种算法的行为。
因此，它的理解无论什么权衡你会做其中涉及的问题，体系结构，与经验的深入理解，才能明白其使用，以及如何调整涉及的常数。
没有人说，O（1）总是比为O（log N）更好。 不过，我可以向你保证，一个O（1）算法也将扩展的方式更好，所以即使你做出了多少用户将系统或数据处理的大小上不正确的假设，都不会有问题该算法。
Answer 15:
是的，对数（N）<100最实用的目的，并且不，你不能总是通过不断更换。
例如，这可能会导致严重的错误估计你的程序的性能。 如果O（N）程序处理在1毫秒1000个元素的数组，则你确定它将处理在1秒（或左右）10个6元件。 如果，虽然，该程序是O（N * logN）的，那么它将把它〜2秒处理10个6个元素。 这种差异可能是至关重要的 - 例如，你可能会认为你已经有足够的服务器电源，因为你每小时3000个请求，你认为你的服务器可以处理多达3600。
另一个例子。 想象一下，你有函数f（）在O（logN）的工作，并在每次迭代调用函数g（），在O（logN）的也有效。 然后，如果你用常量替换这两种日志，你认为你的程序在固定时间内的作品。 现实将是残酷的，但 - 两个日志可以给你高达100 * 100的乘数。
Answer 16:
确定大O符号的规则是，当你不决定O（log n）的简单= O（1）。
作为krzysio说，你可以积累O（log n）的秒，然后他们会做出很明显的差异。 想象一下，你做一个二进制搜索：O（log n）的比较，然后想象，每个比较的复杂度为O（log n）的。 如果你忽略了这两个你O（1），而不是为O（log 2 N）。 同样，你可以在澳莫名其妙地到达（日志10 N），然后你会发现对不太大“N”个很大的区别。
Answer 17:
假设在整个应用程序，为用户等待的最常见的操作90％的时间一个算法账户。
假设实时O（1）操作需要在你的架构的第二和O（logN）的操作基本上0.5秒*日志（N）。 那么，在这一点上，我真的很想你画一个图表，在曲线和直线的交点的箭头，他说，“它在这里很重要。” 你想使用日志（N）运算的小型数据集和大型数据集的O（1）运算，在这种情况下。
大O符号和性能优化是一个学术活动，而不是提供真正价值的用户对于已经便宜的操作，但如果它是一个关键路径上的一个昂贵的操作，那么你赌它很重要！
Answer 18:
对于可以采取不同大小的N个输入的任何算法，它需要操作的数量是上界由某些函数f（N）。
所有大O告诉你的是，函数的形状。
O（1）意味着有一些数A，使得f（N）<A为大N.
O（N）是指有一些甲使得f（N）<AN为大N.
O（N ^ 2）意味着有一些甲使得f（N）<AN ^ 2为大N.
为O（log（N））意味着有一些甲使得f（N）<AlogN大型N.
大O只字未提大A是如何（算法即有多快），或在这些功能互相交叉。 它只是说，当你在比较两种算法，如果他们的大O的不同，再有就是N的值（可能是小的或者也可能是非常大的），其中一个算法将开始优于其他。
Answer 19:
你是对的，在很多情况下，它不会为pracitcal目的关系。 但关键的问题是“增长有多快N”。 我们知道的大部分算法把输入的大小，所以它的增长成线性。
但一些算法具有以复杂的方式导出的N的值。 如果N是“的可能的彩票的组合用于与X不同数字彩票号码”突然重要，如果你的算法是O（1）或O（logN）的
Answer 20:
BIG-OH告诉你一个算法比另一给予一定的常数因子更快。 如果输入意味着一个足够小的常数因子，你可以用一个线性搜索，而不是一个的log（n）搜索一些基地的打算看到了巨大的性能提升。
Answer 21:
为O（log N）可能会产生误导。 就拿上的操作红黑树 。
的操作是O（logN）的但相当复杂的，这意味着许多低层次的操作。
Answer 22:
我不相信有一个大的恒定和O（logN）的算法，在那里你可以自由 O（1）之间进行选择确实存在。 如果有N个元素与一开始工作，它只是普通的不能让它O（1），这是唯一可行的就是将你的N到你的代码的其他部分。
我试图说的是，在所有的真实案例，我知道你关有一定的空间/时间权衡，或者一些前处理如编译数据，以更有效的方式。
也就是说，你不会真的去O（1），你只需动N个部分的其他地方。 要么你换你的代码的某些部分的性能与某些内存量要么你交换另一个你的算法中的一个组成部分的性能。 要保持理智，你应该总是看大图。
我的观点是，如果你有N个项目不能消失。 换句话说，你可以低效为O（n ^ 2）算法或恶化，O（n.logN）之间进行选择：它是一个真正的选择。 但是你从来没有真正去O（1）。
我试图指出的是，为每一个问题和初始数据状态有一个“最好”的算法。 你可以做更坏，但从来没有好。 有了一定的经验，你可以拥有的，这是什么intrisic复杂了良好的猜测。 然后，如果你的整体治疗相匹配，你知道你有什么事情的复杂性。 你将不能够降低复杂性，而只是将其移动。
如果问题是O（n），它会不会成为O（logN）的或O（1），你只是增加一些预处理，使得整体的复杂性是不变的或者更糟，并有可能后面的步骤会有所改善。 请说出您想阵列的小元件，可以在O（N）搜索或使用那么任何常见O（NLogN）排序处理对数组进行排序有使用了O的第一（1）。
这是个好主意，这样做随随便便？ 只有当你的问题也问了第二，第三等元素。 然后您最初的问题是真正的O（NLogN），而不是O（N）。
它是不一样的，如果你等待十倍或者二十倍不再为你的结果，因为你说的简化O（1）= O（LOGN）。
我在等待一个反例;-)那就是你有O（1）和O（LOGN）和，每一个O（LOGN）步不会比在O（1）之间选择任何真实的案例。 所有你能做的就是把一个糟糕的算法，而不是一个自然的或移动的一些重治疗到较大的图片的其他部分（的计算结果前，使用的存储空间等）
Answer 23:
比方说，你使用了一个O的图像处理算法（日志N），其中N是图像的数量。 现在...说明它在固定时间内运行将使一个认为，无论多少图像有，它仍然会完成它的任务大约相同数量的时间。 如果单个图像上运行的算法将假设需要一整天的时间，并假设O（logn）时间将不会超过100 ...想象这个人会尝试一个非常大的图像数据库上运行的算法惊喜 - 他希望它在一天左右做...但它会采取个月，它完成。
文章来源: O(log N) == O(1) - Why not?
