PROSAGA码农传奇-Xedge-Big-O表示法什么时候失败？

17 条回复

0#
回复此人
5678 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 简答：当n很小时。当您只有三个目的地时，快速解决旅行商问题（但是，在万亿元素列表中找到最小数字可以持续一段时间，尽管这是O（n）。） </p> </DIV>

编辑
1#
回复此人
小鬼 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 简短的回答：当你开始使用大量内存时，总是在现代硬件上。教科书假设内存访问是统一的，而不再是。您当然可以对非统一访问模型进行Big O分析，但这有点复杂。 </p> <P> 小n个案例很明显但并不有趣：足够快就足够了。 </p> <P> 实际上，我在使用Delphi，Java，C＃和Smalltalk中的标准集合时遇到了几百万个对象的问题。对于较小的那些，主要因素被证明是散列函数或比较 </p> </DIV>

编辑
2#
回复此人
大魔王 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 当N很小时，常数因子占主导地位。查找五个项目数组中的项目可能比在哈希表中查找项目更快。 </p> </DIV>

编辑
3#
回复此人
Ni | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> Big-Oh表示法失败的一个广泛领域是数据量超过可用RAM量。 </p> <P> 使用排序作为示例，排序所花费的时间量不受比较或交换的数量（在最佳情况下分别具有O（n log n）和O（n））的支配。时间量由磁盘操作数量决定：块写入和块读取。 </p> <P> 为了更好地分析处理超过可用RAM的数据的算法，I / O模型诞生了，您可以计算磁盘读取的数量。在那里，您考虑三个参数： </p> <UL> <LI> 元素数量N; </LI> <LI> 内存量（RAM），M（可以在内存中的元素数量）;和 </LI> <LI> 磁盘块的大小B（每个块的元素数）。 </LI> </UL> <P> 值得注意的是磁盘空间量不足;这被视为无限。典型的额外假设是M> 1。乙 <SUP> 2 </SUP> 。 </p> <P> 继续排序示例，您通常喜欢I / O情况下的合并排序：将元素划分为大小（M）的块并在内存中排序（例如，快速排序）。然后，通过从每个块读取第一个块到内存中来合并它们（M / B），将所有元素填充到堆中，并重复选择最小元素，直到您选择了它们中的B为止。将此新合并块写出并继续。如果您耗尽了其中一个读入内存的块，请从同一块中读取一个新块并将其放入堆中。 </p> <P> （所有表达都应该被认为是大的）。您形成N / M排序的块然后合并。合并N / M次的log（base M / B）;每次读取和写入所有N / B块时，都需要N / B *（N / M的基数M / B）时间。 </p> <P> 您可以分析内存中的排序算法（适当修改以包括块读取和块写入），并且看到它们的效率远低于我提供的合并排序。 </p> <P> 这些知识是由我的I / O算法课程提供的，由Arge和Brodal提供（ <a href="http://daimi.au.dk/~large/ioS08/" rel="nofollow noreferrer"> http://daimi.au.dk/~large/ioS08/ </A> ）;我还进行了验证理论的实验：一旦超过内存，堆排序就会“几乎无限”。快速排序变得无法忍受缓慢，合并排序几乎非常缓慢，I / O效率合并排序表现良好（最好的一堆）。 </p> </DIV>

编辑
4#
回复此人
流浪海。 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> Robert Sedgewick在他的Coursera课程中讨论了关于算法分析的大O符号的缺点。他称之为特别令人震惊的例子 <EM> 银河算法 </EM> 因为虽然他们可能比他们的前辈有更好的复杂性等级，但它需要输入天文尺寸才能在实践中显示出来。 </p> <P> <a href="https://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf" rel="nofollow"> https://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf </A> </p> </DIV>

编辑
5#
回复此人
WL | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 的<strong> 当您的数据不适合模型时 </强> ，big-o表示法仍然有效，但你会看到最佳和最差情况的重叠。 </p> <P> 也，的<strong> 一些操作被调整为线性数据访问与随机数据访问 </强> 因此，如果调用它的方法从设计变化，那么一个算法虽然在循环方面优越，但可能会很慢。同样的，的<strong> 如果算法导致页面/缓存未命中 </强> 由于它访问内存的方式，Big-O无法准确估计运行流程的成本。 </p> <P> 显然，正如我已经忘记的那样的<strong> 当N很小时 </强> :) </p> </DIV>

编辑
6#
回复此人
部落用户 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> Big-O描述了算法的效率/复杂性，而不一定描述了给定代码块的实现的运行时间。这并不意味着Big-O失败了。这只意味着它并不意味着预测运行时间。 </p> <P> 看看答案 <a href="https://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o"> 这个问题 </A> 对于Big-O的一个很好的定义。 </p> </DIV>

编辑
7#
回复此人
v-star*위위 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 一般的答案是，Big-O允许你通过隐藏常数因素而变得非常草率。正如问题中所提到的，Fibonacci Heaps的使用就是一个例子。斐波纳契堆 <EM> 做 </EM> 具有很好的渐近运行时间，但在实践中，常量因子太大而无法用于现实生活中遇到的数据集的大小。 </p> <P> Fibonacci堆通常用于证明图相关算法的渐近复杂度的良好下界。 </p> <P> 另一个类似的例子是 <a href="http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm" rel="nofollow noreferrer"> Coppersmith-Winograd算法 </A> 用于矩阵乘法。它是目前用于矩阵乘法的最快已知渐近运行时间的算法，O（n <SUP> 2.376 </SUP> ）。但是，它的常数因素实在太大而不适用。与Fibonacci Heaps一样，它经常被用作其他算法的构建块来证明理论时间界限。 </p> </DIV>

编辑
8#
回复此人
雪浴冰灵 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 我已经看到一些情况，随着数据集的增长，算法的复杂性变得不如内存访问模式重要。在某些情况下，使用智能算法导航大型数据结构会导致更多的页面错误或缓存未命中，而不是使用更糟糕的大O的算法。 </p> <P> 对于小n，两种算法可以是可比较的。随着n的增加，更智能的算法表现更好。但是，在某些时候，n增长到足以使系统屈服于内存压力，在这种情况下，“更糟糕”的算法实际上可能表现得更好，因为常量基本上是重置的。 </p> <P> 但这并不是特别有趣。当你到达这个反转点时，两种算法的性能通常是不可接受的，你必须找到一种新算法，它具有更友好的内存访问模式和更好的大O复杂性。 </p> </DIV>

编辑
9#
回复此人
烏鴉喝酒 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 规范的例子是Quicksort，它的最短时间是O（n ^ 2），而Heapsort是O（n logn）。然而，在实践中，Quicksort通常比Heapsort更快。为什么？两个原因： </p> <UL> <LI> <P> Quicksort中的每次迭代都比Heapsort简单得多。更重要的是，它可以通过简单的缓存策略轻松优化。 </p> </LI> <LI> <P> 最坏的情况很难打。 </p> </LI> </UL> <P> 但恕我直言，这并不意味着“大O失败”。第一个因素（迭代时间）很容易纳入您的估算。毕竟，大O数应该乘以这个几乎恒定的事实。 </p> <P> 如果你得到的是摊销数字而不是平均数，那么第二个因素会消失。他们可能更难估计，但讲述更完整的故事 </p> </DIV>

编辑
10#
回复此人
Hey ou | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 这在某种程度上取决于Big-O测量的内容 - 当它是最糟糕的情况时，它通常会“失败”，因为运行时性能将比Big-O建议的要好得多。如果是平均情况，则可能会更糟。 </p> <P> 如果算法的输入数据具有某些先验信息，则Big-O表示法通常“失败”。通常，Big-O表示法指的是最坏的情况复杂性 - 如果数据完全随机或完全非随机，通常会发生这种情况。 </p> <P> 例如，如果您将数据提供给已分析的算法且big-o基于随机数据，但您的数据具有非常明确的结构，则结果时间可能比预期快得多。同样地，如果您正在测量平均复杂度，并且您提供的数据非常随机，那么算法的执行可能会比预期的要糟糕得多。 </p> </DIV>

编辑
11#
回复此人
你咖喱人biss嗷 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> Big O失败的一个方面是内存访问模式。 Big O仅计算需要执行的操作 - 如果算法导致更多缓存未命中或需要从磁盘中分页的数据，则无法跟踪。对于小N，这些效应通常占主导地位。例如，由于存储器访问，通过100个整数的数组的线性搜索可能会通过100个整数的二叉树击败搜索，即使二叉树很可能需要较少的操作。每个树节点将导致高速缓存未命中，而线性搜索将主要针对每次查找命中高速缓存。 </p> </DIV>

编辑
12#
回复此人
时间 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 它恰好在一种情况下失败：当人们试图将它用于某些它不适合的东西时。 </p> <P> 它告诉你算法如何扩展。它没有告诉你它有多快。 </p> <P> Big-O表示法并不能告诉您在任何特定情况下哪种算法会更快。它只告诉你，对于足够大的输入，一个将比另一个更快。 </p> </DIV>

编辑
13#
回复此人
猫南北 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 一个例子（我不是专家）是线性编程的单纯形算法在任意输入上具有指数最坏情况复杂性，即使它们在实践中表现良好。一个有趣的解决方案是考虑“平滑的复杂性”，它通过查看任意输入的小随机扰动来混合最坏情况和平均情况性能。 </p> <P> <a href="http://reference.kfupm.edu.sa/content/s/m/smoothed_analysis_of_algorithms__why_the_110204.pdf" rel="nofollow noreferrer"> 斯皮尔曼和腾（2004） </A> 能够证明阴影顶点单纯形算法具有多项式平滑复杂度。 </p> </DIV>

编辑
14#
回复此人
一号位 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <OL> <LI> 小N - 对于今天的电脑来说，100可能太小而无法担心。 </LI> <LI> 隐藏乘数 - IE合并与快速排序。 </LI> <LI> 病理案例 - 再次，合并与快速 </LI> </醇> </DIV>

编辑
15#
回复此人
威斯特 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 这个问题就像在问“一个人的智商何时在实践中失败？”很明显，拥有高智商并不意味着你会在生活中取得成功，智商低并不意味着你会死亡。然而，我们将智商作为评估潜力的一种手段来衡量，即使它不是绝对的。 </p> <P> 在算法中，Big-Oh表示法为您提供算法的IQ。这并不一定意味着算法对于您的特定情况将表现最佳，但是有一些数学基础表明该算法具有一些良好的潜力。如果Big-Oh表示法足以衡量性能，您会看到更多的内容并减少运行时测试。 </p> <P> 把Big-Oh想象成一个范围而不是一个更好或更差的具体指标。最佳案例场景和最坏情况场景以及介于两者之间的大量场景。根据它们在Big-Oh范围内的适合程度选择算法，但不要将符号作为测量性能的绝对值。 </p> </DIV>

编辑

登录后才能参与评论