\begingroup

我一直在努力理解计算机科学中普遍接受的观念:指数算法效率低下。标准解释是它们“随着输入的大小呈指数增长”,但这种解释听起来不太令人满意。它没有完全解释为什么指数增长会特别导致这些算法在我们的物理世界中不切实际。

例如,考虑一个假设的思维实验,其中来自另一个宇宙(指数算法可以高效运行)的智能外星人询问为什么这些算法在这里效率低下。说“因为它们呈指数增长”并不能解释太多。外星人可能仍然感到困惑,因为指数增长本身并不是一个问题;是我们物理世界的局限性造成了这个问题。

我正在寻找科学论文或教科书的参考资料,甚至是对这个主题进行全面研究的答案,包括支持为什么指数算法与多项式算法相比效率低下的数据或理论推理。我发现的大多数计算机科学教科书和资源通常将重点限制在多项式时间算法上,而没有深入研究这些分类背后的更深层次的推理或证据。在这个假设的场景中,我们应该如何回答外星人的问题?

此外,我们该如何区分高效算法和低效算法?任何比多项式时间算法耗时更长的算法都被认为是低效的吗?

我已经看过类似的问题:

\endgroup

2

  • \begingroup
    如果您认为“高效”是“就至少一个可能超过某个小常数的输入而言,呈渐近指数(或更糟)”的简写(如果我们知道 m 永远不会超过 5,那么 O(n^2 + 2^m) 的算法将被称为 O(n^2)),而不是“高效”是一个正式的概念,我们发现它的边界是 O(2^n)。还有许多多项式时间算法效率太低,不实用。只是几乎所有指数算法都是如此,所以这就是(有点随意的)界限。
    \endgroup


    – 


  • \begingroup
    框架挑战:在算法中,“高效”(未指定定义)通常意味着某种东西比以前的方法更有效(相对于以前的方法),而不是对多项式时间的特定要求。
    \endgroup


    – 


最佳答案
3

\begingroup

在我们的一生中(或在太阳系的生命周期内等),任何无法执行的算法都很难被视为“有效的”。

对于每个相当中等规模的问题实例,指数时间算法在我们的一生中都是不可行的。例如,合理的物理模型表明,也许101001010010^{100}如果你把整个宇宙的质量都放到一台大型并行计算机中,那么在你的一生中,你的计算步骤数将达到 10 …2n2n2^n计算步骤,然后一次n≥340n340n\ge 340,算法不会在你的一生中终止。

因此,一般来说,如果您只需要在非常小的问题实例上使用指数时间算法,那么它只能被视为“有效的”。

当然,没有“计算警察”来严格定义“高效”这个词。您可以根据自己的目的设定任何标准,以决定什么才是足够高效的。尽管如此,我希望这说明了在任何非平凡规模的问题上使用指数时间算法所面临的根本挑战。

\endgroup

\begingroup

如果算法或实现花费的时间超过必要时间,则该算法或实现“效率低下”。有些问题很难。没有快速算法,因为问题太难了。一个算法需要2n2n2^n步骤很慢,但由于问题的难度,它可能是可用的最高效算法。但另一种需要 n! 步骤的算法花费的时间比需要的时间长得多,因此效率低下。

你要找的词是“不可行”。出于物理原因(量子物理导致任何状态变化所需的最小能量,宇宙中的总能量),任何计算在物理上都不可能超过225622562^{256}步骤。如果你计算在我的孙辈的一生中,使用地球上的所有资源可以完成的最大步骤数,那么这个数字要小得多。如果算法不能在这些限制下运行,那么它是不可行的。

外星人应该完全有能力将操作数量转化为所需的资源,而且他们的可行性极限不会比我们高太多。

\endgroup

\begingroup

算法分析的关键思想之一是能够评估运行时间如何随着输入大小的变化而变化。

考虑以下列表nnn元素。

  1. 说一个算法以线性时间运行意味着,当你向列表中添加一个元素时,运行时间将增加 1ms。如果你再次向列表中添加另一个元素,运行时间将再次增加 1ms。如果你将元素数量增加一倍,那么它将花费两倍的时间。如果你将元素数量增加三倍,那么它将花费三倍的时间。依此类推。

  2. 假设一个算法以指数时间运行(比如说2n2n2^n) 意味着,当你向列表中添加一个元素时,运行时间将加倍。如果你再添加一个元素,运行时间将相对于初始列表增加四倍。如果你将列表的长度加倍,甚至没有办法简洁地说明会发生什么。

要理解为什么这是“低效的”,你应该反思两件事:

  • 没有太多的倍增空间:我们目前对物理学的理解有5.39 ×10445.39×10四十四5.39 \times 10^{−44}秒是最小的有意义的时间单位;我们目前对宇宙的理解是为 137.87 亿年。如果你从普朗克时间单位开始,不断将时间翻倍,那么要经过大约 200 次翻倍才能得到宇宙的年龄。从最小到最大的时间单位,你只能翻倍几百次。请记住,计算机的最小时间单位比普朗克单位大得多;我们想要运行算法来获得结果的时间跨度比宇宙的年龄小得多。

  • 我们通常要处理数十、数百、数千个事物;确实很多:我们应用算法来解决现实世界的问题。但即使是用于教学的玩具示例通常也涉及数十或数百个对象。在现实世界中,我们的列表可能是公司的客户、图书馆的书籍;我们的图表可能是城市地图的模型,或网络中的页面。数百万个对象或更多。

结合这些因素,我们可以得出这样的结论:虽然你可以在输入上运行指数时间算法,但n = 2n=2n=2元素,没有太多空间nnn增长;但现实世界中有趣的事例很有可能nnn数百,数千,数百万等等

\endgroup