我真的很好奇有哪些现实世界的例子不符合这个规律。对于所有实际目的,log(无穷大) < 100。
为了澄清:
- 我理解O(f(N))。
- 我想知道现实世界的例子,其中渐近行为比实际性能的常数更重要。
- 如果log(N)可以被一个常数替换,那么它仍然可以在O(N log N)中被一个常数替换。
我真的很好奇有哪些现实世界的例子不符合这个规律。对于所有实际目的,log(无穷大) < 100。
大 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 个元素,例如字节数组。但它可以是任何东西,包括文件中的字节数。
我认为这是一种实用的方法;O(logN)永远不会超过64。在实践中,每当术语变得像O(logN)这样“小”时,您就必须测量以查看常数因子是否胜出。另请参见
引用我自己在另一个答案评论中的话:
[大O符号]“分析”只对至少为O(N)的因子有影响。对于任何较小的因子,大O符号分析都是无用的,您必须进行测量。
和
“使用O(logN)时,输入大小确实很重要。”这就是问题的重点。当然,这很重要...在理论上。 OP问的问题是,在实践中是否重要?我认为答案是否定的,没有,也永远不会有一个数据集,logN增长得如此之快,以至于始终可以击败常数时间算法。即使对于我们孙辈的寿命中最大的实际数据集,logN算法也有不错的机会打败常数时间算法-您必须始终进行测量。
编辑
一次很好的演讲:
http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey
关于一半的时候,Rich讨论了Clojure的哈希尝试,它们显然是O(logN),但对数的底很大,因此即使包含40亿个值,trie的深度也最多为6。在这里,“6”仍然是O(logN)值,但它是一个非常小的值,因此选择放弃这个神奇的数据结构,因为“我真的需要O(1)”是一件愚蠢的事情。这强调了对于想要算法“运行快速”和“扩展良好”的实用主义者来说,大多数其他答案都从“理论”角度上来看是错误的。编辑
另请参见
http://queue.acm.org/detail.cfm?id=1814327
这段文字说:
如果这些操作会导致页面错误和缓慢的磁盘操作,那么一个O(log2(n))算法有什么用处呢?对于大多数相关数据集,一个避免页面错误的O(n)甚至O(n^2)算法将比它更快。
(但是请阅读文章以了解上下文)。
O(N)
? - John这是一个常见的误解 - 请记住大O符号并不是告诉你算法在给定值下的绝对性能,它只是告诉你随着输入大小增加算法的行为。
如果你把它放在这个上下文中考虑,就会清楚为什么算法A ~ O(logN)和算法B ~ O(1)是不同的:
如果我在大小为a的输入上运行A,然后在大小为1000000 * a的输入上运行A,则第二个输入需要的时间将比第一个输入多log(1,000,000)倍
如果我在大小为a的输入上运行B,然后在大小为1000000 * a的输入上运行B,则第二个输入需要的时间将与第一个输入大致相同
编辑:重新思考了一下您的问题,我认为其中有些智慧。虽然我永远不会说O(lgN) == O(1)是正确的,但是可能会使用O(lgN)算法而不是O(1)算法。这回到了上面关于绝对性能的观点:仅仅知道一个算法是O(1),另一个算法是O(lgN)是不足以断言应该使用O(1)而不是O(lgN),根据您可能的输入范围,使用O(lgN)可能会更好。
在你描述的方式中,等式是一种常见的滥用符号。
为了澄清:我们通常写成 f(x) = O(logN) 来表示“f(x) 是 O(logN)”。
无论如何,O(1)
意味着无论输入集合有多大,执行一个操作所需的步骤/时间都是恒定的(作为上限)。但对于 O(logN)
,步骤/时间数量仍然随着输入大小(其对数)而增长,只是增长得非常缓慢。对于大多数实际应用程序,您可以放心地假设这个步骤数不会超过100,但我敢打赌,存在多个数据集足够大,以至于您的声明既危险又无效(数据包跟踪、环境测量等)。
O(log n)
通常与 O(1)
难以区分,这是一个好的观点。O(log n)
算法通常与像全知这样的 O(1)
算法难以区分。O(log n)
算法,因为它们通常与常数时间难以区分,并且它们通常比线性时间算法表现出色。n=3
端。O(log n)
。