具有O(n log n)时间和O(1)空间复杂度与O(n)时间和O(n)空间复杂度的算法

Question

我很想知道哪种算法更好:

• 具有O(n log n)时间和O(1)空间复杂度的算法
• 具有O(n)时间和O(n)空间复杂度的算法

在O(n long n)时间和恒定空间中求解的大多数算法可以在O(n)时间内通过在空间方面支付罚分来求解.哪种算法更好？我如何决定这两个参数？

示例:数组对总和

1. 可以通过排序在O(n logn)时间内解决
2. 可以在O(n)时间使用散列映射来解决,但是使用O(n)空间

Answer 1

没有实际测试任何东西(一个冒险的举动!),我将声称O(n log n) - 时间,O(1) - 空间算法可能比O(n)时间更快,O(n ) - 空间算法,但仍可能不是最优算法.

首先,让我们从高层次的角度讨论这个问题,忽略您所描述的算法的特定细节.需要记住的一个细节是,尽管O(n)-time算法渐近地比O(n log n)时间算法快,但它们只是通过对数因子更快.请记住,宇宙中的原子数约为10 ⁸⁰(谢谢,物理!),宇宙中原子数的基数为2的对数约为240.从实际角度来看,这意味着您可以将额外的O(log n)因子视为常数.因此,要确定O(n log n)算法是否比特定输入上的O(n)算法更快或更慢,您需要更多地了解big-O表示法隐藏的常量.例如,对于适合宇宙中的任何n,在时间600n中运行的算法将比在时间2n log n中运行的算法慢.因此,就挂钟性能而言,要评估哪种算法更快,您可能需要对算法进行一些分析,以确定哪种算法更快.

然后是缓存和引用局部性的影响.计算机存储器中有大量的高速缓存,这些高速缓存针对读写彼此相邻的情况进行了优化.高速缓存未命中的成本可能很大 - 比命中慢几百或几千倍 - 因此您希望尽量减少这种情况.如果算法使用O(n)内存,那么当n变大时,您需要开始担心内存访问的紧密程度.如果它们分散开来,那么缓存未命中的成本可能会相当快地加起来,从而显着提高隐藏在时间复杂度的大O符号中的系数.如果它们更顺序,那么你可能不需要太担心这一点.

您还需要注意可用的总内存.如果你的系统上有8GB的RAM并且得到一个具有10亿个32位整数的数组,那么如果你需要O(n)辅助空间甚至是一个合理的常数,那么你将无法适应你的辅助存储器进入主内存,它将开始被操作系统分页,真正杀死你的运行时.

最后,存在随机性问题.基于散列的算法预计会有快速运行时间,但是如果你得到一个糟糕的散列函数,那么算法可能会变慢.生成好的随机位很难,因此大多数哈希表只是用于"相当好"的哈希函数,冒着最坏情况输入的风险,这会使算法的性能退化.

那么这些问题在实践中如何实际发挥作用呢？好吧,让我们来看看算法.O(n)-time,O(n)-space算法通过构建数组中所有元素的哈希表来工作,这样您就可以轻松检查数组中是否存在给定元素,然后扫描数组和看是否有一对总计达到总和.让我们考虑一下上述因素,该算法的工作原理.

• 内存使用量为O(n),并且由于散列的工作方式,对散列表的访问不太可能是顺序的(理想的散列表将具有相当多的随机访问模式).这意味着你将有很多缓存未命中.

• 高内存使用意味着对于大输入,您必须担心内存被进入和退出,从而加剧了上述问题.

• 由于上述两个因素,隐藏在O(n)运行时中的常量项可能比它看起来要高得多.

• 散列不是最坏情况下的效率,因此可能存在导致性能显着降低的输入.

现在,考虑一下O(n log n)-time,O(1)空间算法,它通过进行就地数组排序(比如heapsort)来工作,然后从左到右向内走,看看你是否可以找到一对与目标相加的对.这个过程的第二步具有出色的引用局部性 - 几乎所有的数组访问都是相邻的 - 而且几乎所有的缓存未命中都将在分类步骤中完成.这将增加隐藏在big-O表示法中的常数因子.但是,该算法没有退化输入,其低内存占用可能意味着引用的位置将优于哈希表方法.因此,如果我不得不猜测,我会把钱花在这个算法上.

......好吧,实际上,我把钱花在了第三个算法上:一个O(n log n)时间,O(log n)空间算法基本上就是上面的算法,但是使用了introsort而不是heapsort.Introsort是一个O(n log n)时间,O(log n)空间算法,它使用随机快速排序来对数组进行排序,如果快速排序看起来即将退化,并进行最终插入排序,则切换到heapsort清理一切.Quicksort具有惊人的引用位置 - 这就是为什么它如此之快 - 并且插入排序在小输入上更快,因此这是一个很好的折衷方案.另外,O(log n)额外内存基本上没什么 - 记住,在实践中,log n最多为240.此算法具有您可以获得的最佳参考局部性,给出了O隐藏的非常低的常数因子( n log n)term,

当然,我也必须符合这个答案.我上面做的分析假设我们正在谈论算法的相当大的输入.如果你只是看小输入,那么整个分析就会消失,因为我考虑的效果不会开始出现.在这种情况下,最好的选择就是分析方法,看看哪种方法效果最好.从那里,您可以构建一种"混合"方法,在这种方法中,您可以在一个大小范围内使用一种算法进行输入,在不同大小范围内使用不同的算法进行输入.有可能这会给出一种优于任何一种方法的方法.

也就是说,用Don Knuth的话来说,"要注意上面的分析 - 我只是证明它是正确的,而不是真的尝试过它." 最好的选择是分析一切,看看它是如何工作的.我没有这样做的原因是要分析哪些因素需要注意,并强调比较两种算法的纯粹大O分析的弱点.我希望这种做法能够证明这一点!如果没有,我很乐意看到我弄错了.:-)

Answer 2

从经验来看:

• 如果你绝对无法承受这个空间,请前往O(1)空间路线.
• 当随机访问不可避免时,请前往O(n)空间路径.(它通常更简单,时间常数更小.)
• 当随机访问很慢(例如,寻道时间)时,请前往O(1)空间路线.(你通常可以找到一种缓存连贯的方法.)
• 否则,随机访问速度很快 - 超过O(n)空间路径.(它通常更简单,时间常数更小.)

请注意,如果问题适合内存比瓶颈存储更快,则通常随机访问是"快速的".(例如,如果磁盘是瓶颈,主内存足够快以便随机访问 - 如果主内存是瓶颈,CPU缓存足够快以便随机访问)