performance - O(log N) == O(1) - 为什么不呢？

Question

每当我考虑算法/数据结构时，我都倾向于用常量替换 log(N) 部分。哦，我知道 log(N) 会发散 - 但它在现实世界的应用程序中重要吗？

log(infinity) < 100 for all practical purposes.

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

澄清一下:

• 我理解 O(f(N))
• 我很好奇真实世界的例子，在这些例子中，渐近行为比实际表现的常数更重要。
• 如果 log(N) 可以用常量替换，它仍然可以用 O( N log N) 中的常量替换。

这个问题是为了 (a) 娱乐和 (b) 收集论据，以便在我(再次)遇到关于设计性能的争议时使用。

Answer 1

大 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) 的操作。

另请记住，任何事物的 Big-O 都可能有恒定的开销。假设常量开销是 100 万。对于 O(1)，恒定的开销不会像 O(logn) 那样放大操作数。

还有一点，大家想到的就是O(logn)代表树状数据结构的n个元素为例。但它可以是任何东西，包括文件中的字节。