为什么算法的顺序通常比处理器的速度更重要？
Why is the order of an algorithm generally more important than the speed of the processor?
所以，我知道效率是由算法和数据结构决定的
在溶液中使用。但是，我真的不明白算法的顺序为什么比处理器的速度更重要？
不能说算法的顺序 more/less 比 CPU 速度重要！！！他们没有可比性！！！！
我们使用命令来相互比较不同的算法，因为我们不知道算法将 运行 的目标架构。另外请注意，程序的执行时间取决于许多因素，例如缓存未命中率、主内存命中率和....因此每次执行程序的执行时间可能与之前的不同。结果 我们无法比较两个程序，即使是在一个结构上执行它们也是如此！
一台典型的个人电脑可以做到 10^8 calculations per second。
而世界上最快的超级计算机 10^16 calculations per second。
所以假设您现在 laptop/desktop 上有一个 O(n) 算法 运行。并且在世界上最快的超级计算机上同时执行 O(n^2) 算法 运行。如果 n = 10^10,
运行 PC 上的时间 = 10^10 / 10^8 = 100 seconds。
运行 超级计算机上的时间 = 10^20 / 10^16 = 10000 seconds。
很明显，笔记本电脑的性能远远超过超级计算机。并且在使用更好的算法时实际上快了 100 倍。
我们寻找更好算法的另一个原因是 scalability problem. According to moore's law，计算能力每 18 个月翻一番。因此，即使一台超级计算机今天可以非常快地处理大量输入，但在未来 18 个月内，当问题规模增加许多倍而计算能力只会翻一番时，它可能无法做到这一点。
我尽量通俗易懂地解释一下。
处理器速度以 cycles/sec 衡量，并且因处理器而异。要判断算法，我们需要一个独立于此且完全基于算法的指标。
假设算法中的单个操作需要一个处理器周期。
因此，对于算法 n 的阶数，如果输入的大小为 n，则需要 n 个处理器周期。
如果顺序是算法 n^2，如果输入大小是 n，则需要 n^2 个处理器周期。
所以你看，算法的顺序是独立于处理器速度的度量。阶数越低，运行速度越快。
这是一个非常笼统的答案，但我希望它能消除您的疑问。
我们来看一个例子：
你有一个阶数为 O(n^3) 的算法。您是 运行 处理器上可以在 100 毫秒内处理 n = 10 的算法。
如果 n 达到 10000，则该处理器将需要 1158 天。
处理器速度提高一倍只会将时间缩短至 579 天。
即使您能够获得十倍速度的处理器，也仍然需要几个月的时间。
但是用原始处理器上的 O(n^2) 和 运行 阶之一替换该算法会将所需时间减少到 2.8 小时。
是不是更重要要看情况。算法的复杂度与其速度没有直接关系，可能有 "worse" 算法比 "better" 算法更快地解决特定问题实例。正如其他答案所解释的那样，复杂度顺序归结为问题“memory/time 消耗如何随着输入大小增长？”。对于小输入，你不在乎。对于平均输入，您可以对算法进行基准测试，看看哪个算法在您的硬件上运行得更快。问题是意外的大输入：现在你关心十倍数据是否意味着十倍的运算时间，一百倍的等待时间，或者直到宇宙热寂的永无止境的计算。
一个突出的例子是 Windows XP update mechanism。他们正在使用具有指数 运行 时间的算法处理已安装更新列表。这不是问题，而且 运行 可以接受的速度，直到 - 几十年后 - 更新的数量使它成为一个真正的问题。
但作为一名计算机科学家，我有另一个观点可以分享更重要的事情：算法复杂性更有趣。找出具有更好复杂性的算法是一个智力问题。如果您只关心更快的结果，您可以轻松升级您的硬件。您可以获得金钱的处理能力。处理器的速度或多或少仍在提高 - 只要获得它们，您就可以大大加快程序的速度[1]。直到你达到（技术或预算）的边缘，你需要一个更好的算法。那么你有一个虽然坚果要破解。脑筋急转弯。这是纯粹的乐趣！
1：我并不是说让处理器变快是微不足道的。但是用它们来解决问题是:-)
所以，我知道效率是由算法和数据结构决定的 在溶液中使用。但是，我真的不明白算法的顺序为什么比处理器的速度更重要？
不能说算法的顺序 more/less 比 CPU 速度重要！！！他们没有可比性！！！！ 我们使用命令来相互比较不同的算法，因为我们不知道算法将 运行 的目标架构。另外请注意，程序的执行时间取决于许多因素，例如缓存未命中率、主内存命中率和....因此每次执行程序的执行时间可能与之前的不同。结果 我们无法比较两个程序，即使是在一个结构上执行它们也是如此！
一台典型的个人电脑可以做到 10^8 calculations per second。
而世界上最快的超级计算机 10^16 calculations per second。
所以假设您现在 laptop/desktop 上有一个 O(n) 算法 运行。并且在世界上最快的超级计算机上同时执行 O(n^2) 算法 运行。如果 n = 10^10,
运行 PC 上的时间 = 10^10 / 10^8 = 100 seconds。
运行 超级计算机上的时间 = 10^20 / 10^16 = 10000 seconds。
很明显，笔记本电脑的性能远远超过超级计算机。并且在使用更好的算法时实际上快了 100 倍。
我们寻找更好算法的另一个原因是 scalability problem. According to moore's law，计算能力每 18 个月翻一番。因此，即使一台超级计算机今天可以非常快地处理大量输入，但在未来 18 个月内，当问题规模增加许多倍而计算能力只会翻一番时，它可能无法做到这一点。
我尽量通俗易懂地解释一下。
处理器速度以 cycles/sec 衡量，并且因处理器而异。要判断算法，我们需要一个独立于此且完全基于算法的指标。
假设算法中的单个操作需要一个处理器周期。
因此，对于算法 n 的阶数，如果输入的大小为 n，则需要 n 个处理器周期。
如果顺序是算法 n^2，如果输入大小是 n，则需要 n^2 个处理器周期。
所以你看，算法的顺序是独立于处理器速度的度量。阶数越低，运行速度越快。
这是一个非常笼统的答案，但我希望它能消除您的疑问。
我们来看一个例子：
你有一个阶数为 O(n^3) 的算法。您是 运行 处理器上可以在 100 毫秒内处理 n = 10 的算法。
如果 n 达到 10000，则该处理器将需要 1158 天。
处理器速度提高一倍只会将时间缩短至 579 天。
即使您能够获得十倍速度的处理器，也仍然需要几个月的时间。
但是用原始处理器上的 O(n^2) 和 运行 阶之一替换该算法会将所需时间减少到 2.8 小时。
是不是更重要要看情况。算法的复杂度与其速度没有直接关系，可能有 "worse" 算法比 "better" 算法更快地解决特定问题实例。正如其他答案所解释的那样，复杂度顺序归结为问题“memory/time 消耗如何随着输入大小增长？”。对于小输入，你不在乎。对于平均输入，您可以对算法进行基准测试，看看哪个算法在您的硬件上运行得更快。问题是意外的大输入：现在你关心十倍数据是否意味着十倍的运算时间，一百倍的等待时间，或者直到宇宙热寂的永无止境的计算。
一个突出的例子是 Windows XP update mechanism。他们正在使用具有指数 运行 时间的算法处理已安装更新列表。这不是问题，而且 运行 可以接受的速度，直到 - 几十年后 - 更新的数量使它成为一个真正的问题。
但作为一名计算机科学家，我有另一个观点可以分享更重要的事情：算法复杂性更有趣。找出具有更好复杂性的算法是一个智力问题。如果您只关心更快的结果，您可以轻松升级您的硬件。您可以获得金钱的处理能力。处理器的速度或多或少仍在提高 - 只要获得它们，您就可以大大加快程序的速度[1]。直到你达到（技术或预算）的边缘，你需要一个更好的算法。那么你有一个虽然坚果要破解。脑筋急转弯。这是纯粹的乐趣！
1：我并不是说让处理器变快是微不足道的。但是用它们来解决问题是:-)