pho*_*oku 47 algorithm performance big-o computer-science
每当我考虑算法/数据结构时,我倾向于用常数替换log(N)部分.哦,我知道log(N)有所不同 - 但它在现实世界的应用程序中是否重要？
所有实际用途的log(无穷大)<100.
我真的很好奇现实世界的例子,这是不成立的.
澄清:
这个问题是为了(a)娱乐和(b)收集使用的论据,如果我(再次)进行关于设计性能的争议.
Bri*_*ndy 61
Big 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个元素.但它可能包括文件中的字节.
Bri*_*ian 23
我认为这是一种务实的做法; O(logN)永远不会超过64.实际上,每当条件变得像O(logN)一样"小"时,你必须测量以查看常数因子是否胜出.也可以看看
引用自己对另一个答案的评论:
[Big-Oh]'分析'仅对至少为O(N)的因素有用.对于任何较小的因素,大哦分析是无用的,你必须测量.
和
"使用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)算法可避免页面错误,它将围绕它运行圆圈.
(但请阅读上下文中的文章).
Fal*_*ina 20
这是一个常见的错误 - 记住Big O符号并没有告诉你算法在给定值下的绝对性能,它只是在增加输入大小时告诉你算法的行为.
当你在那个环境中使用它时,很明显为什么算法A~O(logN)和算法B~O(1)算法是不同的:
如果我在大小为a的输入上运行A,那么在大小为1000000*a的输入上,我可以期望第二个输入在第一次输入时记录(1,000,000)次
如果我在大小为a的输入上运行B,那么在大小为1000000*a的输入上,我可以预期第二个输入所需的时间大约与第一个输入相同
编辑:再考虑一下你的问题,我认为它有一些智慧.虽然我绝不会说这是正确的说O(LGN)== O(1),它IS可能是一个O(LGN)算法可能会超过一个O(1)算法中使用.这种退约的绝对性能点之上:只要知道一个算法是O(1),另一种算法是O(LGN)是不足够的声明,你应该(1)在O(LGN)使用O,它肯定可能给出您可能的输入范围,O(lgN)可能最适合您.
你问了一个真实的例子.我会给你一个.计算生物学.用ASCII编码的一条DNA链在空间的千兆字节上.典型的数据库显然会有数千个这样的链.
现在,在索引/搜索算法的情况下,当与常量结合时,log(n)倍数会产生很大的差异.之所以？这是您的输入大小是天文数字的应用程序之一.此外,输入大小将始终继续增长.
不可否认,这类问题很少见.这么大的应用程序只有很多.在那些情况下,虽然......它创造了一个与众不同的世界.
平等,你描述的方式,是一种常见的符号滥用.
澄清一下:我们通常写f(x)= O(logN)暗示"f(x)是O(logN)".
无论如何,O(1)无论输入集有多大,都意味着执行动作的常数步数/时间(作为上限).但是O(logN),因为步数/时间的数量仍然随着输入大小(它的对数)的变化而增长,它的增长速度非常慢.对于大多数现实世界的应用程序,您可以安全地假设这个步骤数不会超过100,但我敢打赌,有多个数据集大小足以标记您的语句既危险又无效(数据包跟踪,环境测量和还有很多).
对于足够小的N,O(N ^ N)实际上可以替换为1.不是O(1)(根据定义),但是对于N = 2,您可以将其视为具有4个部分的一个操作,或者是恒定时间操作.
如果所有操作需要1小时怎么办？O(log N)和O(1)之间的差异很大,即使N很小.
或者,如果您需要运行该算法一千万次？好的,花了30分钟,所以当我在数据集上运行它一百倍时,它仍然需要30分钟,因为O(logN)与O(1)"相同"......呃......什么？
你的陈述"我理解O(f(N))"显然是错误的.
真实世界的应用程序,哦......我不知道......每次使用O() - 符号EVER？
例如,在1000万个项目的排序列表中进行二进制搜索.这是我们在数据变得足够大时使用哈希表的原因.如果您认为O(logN)与O(1)相同,那么为什么您会使用哈希而不是二叉树？
正如许多人已经说过的,对于现实世界,你需要先考虑常数因素,然后再担心O(log N)的因素.
然后,考虑一下你期望N是什么.如果您有充分的理由认为N <10,则可以使用线性搜索而不是二进制搜索.那是O(N)而不是O(log N),根据你的灯光会很重要 - 但是根据应用程序,将找到的元素移动到前面的线性搜索可能会胜过更复杂的平衡树.
另一方面,请注意,即使log N不可能超过50,性能因子10也非常大 - 如果您受计算限制,那么这样的因素可以轻松地决定您的应用程序.如果这对你来说还不够,你会经常在算法中看到(log N)^ 2或(logN)^ 3的因子,所以即使你认为你可以忽略一个因子(log N),这并不意味着你可以忽略更多.
最后,请注意,线性编程的单纯形算法具有O(2 ^ n)的最差情况.但是,对于实际问题,最坏的情况永远不会出现; 在实践中,单纯形算法快速,相对简单,因此非常流行.
大约30年前,有人开发了一种用于线性规划的多项式时间算法,但最初并不实用,因为结果太慢了.
如今,有线性编程的实用替代算法(具有多项式时间的情况,值得的),在实践中可以胜过单纯形法.但是,根据问题,单纯形法仍然具有竞争力.
O(log n)通常无法区分的观察结果O(1)是好的观察结果。
作为一个熟悉的示例，假设我们想要在包含 1,000,000,000,000 个元素的排序数组中查找单个元素：
假设我们向正在搜索的数组添加了一个元素，现在我们必须搜索另一个元素：
假设我们将正在搜索的数组中的元素数量加倍，现在我们必须搜索另一个元素：
正如我们从这个例子中看到的，无论出于何种意图和目的，O(log n)像二分搜索这样的算法通常与O(1)像全知这样的算法没有什么区别。
要点是：*我们使用O(log n)算法是因为它们通常与常数时间算法没有区别，而且它们的性能通常比线性时间算法好得多。
显然，这些例子假设了合理的常数。显然，这些都是一般性的观察结果，并不适用于所有情况。显然，这些点适用于曲线的渐近端，而不是n=3末端。
但这一观察结果解释了为什么我们使用诸如调整查询之类的技术来执行索引查找而不是表扫描 - 因为无论数据集大小如何，索引查找都以几乎恒定的时间运行，而表扫描则在在足够大的数据集上速度极其缓慢。索引查找是O(log n).