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

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

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

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

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

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

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

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

考虑以下列表nnn元素。

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

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

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

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

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

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