O（日志N）== O（1） - 为什么不呢？ [英] O(log N) == O(1) - Why not?

问题描述

每当我考虑算法/数据结构我倾向于常量替换日志（N）的部件。哦，我知道的log（n）发散 - 但它在实际应用中重要

Whenever I consider algorithms/data structures I tend to replace the log(N) parts by constants. Oh, I know log(N) diverges - but does it matter in real world applications?

日志（无穷大）＆LT; 100所有的实际目的。

log(infinity) < 100 for all practical purposes.

我真的很好奇现实世界的例子，这不成立。

I am really curious for real world examples where this doesn't hold.

要澄清：

• 在我的理解O（F（N））
• 在我好奇的现实世界的例子，在渐近行为的重要多于实际性能的常量
• 如果日志（N），可以用一个常数代替它仍然可以通过一个常数的O（N日志N）。

• I understand O(f(N))
• I am curious about real world examples where the asymptotic behaviour matters more than the constants of the actual performance.
• If log(N) can be replaced by a constant it still can be replaced by a constant in O( N log N).

这个问题是（一）娱乐和（b）为了搜集论据，如果我运行（再次）使用到一个关于设计的性能争议。

This question is for the sake of (a) entertainment and (b) to gather arguments to use if I run (again) into a controversy about the performance of a design.

推荐答案

我觉得这是一个务实的做法; O（logN）的绝不会超过64。在实践中，只要条件得到尽可能'小'为O（LOGN）你必须测量，看是否恒定因素胜出。另请参见

I think this is a pragmatic approach; O(logN) will never be more than 64. In practice, whenever terms get as 'small' as O(logN), you have to measure to see if the constant factors win out. See also

<一个href="http://stackoverflow.com/questions/1424303/uses-of-ackermann-function/1424397#1424397">http://stackoverflow.com/questions/1424303/uses-of-ackermann-function/1424397#1424397

要引用自己的意见另一个回答：

To quote myself from comments on another answer:

[大哦]'分析'只针对因素事宜   这是至少O（N）。对于任何   较小的因素，大哦分析   没用的，你必须衡量的。

[Big-Oh] 'Analysis' only matters for factors that are at least O(N). For any smaller factor, big-oh analysis is useless and you must measure.

和

带O（logN）的你输入的大小做   此事。这是整点   的问题。当然，它的事项？   理论上的。在OP问的问题   是，这很重要的实际上的？一世   争辩说，答案是否定的，有   是不是，也永远不会成为一个数据集   为此将logN个增长如此之快，以   总是被打的恒定时间   算法。即使对于最大的   实际数据集想象的   我们的孙子的一生，一个logN个   算法具有殴打一个公平的机会   恒定时间算法 - 你必须   经常测量。

"With O(logN) your input size does matter." This is the whole point of the question. Of course it matters... in theory. The question the OP asks is, does it matter in practice? I contend that the answer is no, there is not, and never will be, a data set for which logN will grow so fast as to always be beaten a constant-time algorithm. Even for the largest practical dataset imaginable in the lifetimes of our grandchildren, a logN algorithm has a fair chance of beating a constant time algorithm - you must always measure.

修改

有一个很好的谈话：

<一个href="http://www.infoq.com/$p$psentations/Value-Identity-State-Rich-Hickey">http://www.infoq.com/$p$psentations/Value-Identity-State-Rich-Hickey

大约一​​半，富讨论Clojure的散列尝试，这显然是O（logN个），但对数的底数大，所以该线索的深度为至多6，即使它包含4十亿值。这里的6仍然是一个O（logN）的价值，但它是一个非常小的值，所以选择放弃这个真棒数据结构，因为我真的需要O（1）是一个愚蠢的事情。这强调了如何大多数其他这个问题的答案是简单的错误的从实用主义的角度来看谁希望自己的算法，跑得快和很好地扩展，不管什么样的理论说：

about halfway through, Rich discusses Clojure's hash tries, which are clearly O(logN), but the base of the logarithm is large and so the depth of the trie is at most 6 even if it contains 4 billion values. Here "6" is still an O(logN) value, but it is an incredibly small value, and so choosing to discard this awesome data structure because "I really need O(1)" is a foolish thing to do. This emphasizes how most of the other answers to this question are simply wrong from the perspective of the pragmatist who wants their algorithm to "run fast" and "scale well", regardless of what the "theory" says.

修改

另请参见

http://queue.acm.org/detail.cfm?id=1814327

它说

有什么好处是O（LOG2（n））的算法   如果这些行动导致页面错误   和缓慢的磁盘操作？对于大多数   有关数据集的O（N），甚至是   为O（n ^ 2）算法，避免了页   故障，将运行兜圈子了。

What good is an O(log2(n)) algorithm if those operations cause page faults and slow disk operations? For most relevant datasets an O(n) or even an O(n^2) algorithm, which avoids page faults, will run circles around it.

（但去阅读文章的上下文中）。

(but go read the article for context).

这篇关于O（日志N）== O（1） - 为什么不呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！