algorithm - 效率/算法与系统规范

Question

我们都在谈论算法的效率，它基本上取决于输入大小。

运行该算法的当前计算机的系统规范如何？在 Core 2 Duo 2.6 GHZ、4 GB RAM 计算机或 P-2、256 MB RAM 计算机中运行不同的排序算法有什么不同吗？

我确信一定存在性能差异。但是，我想知道算法和系统规范之间的真正关系是什么......

Answer 1

硬件性能的提高将使您的算法运行时间增加 C 倍。这意味着如果您的计算机 A 总体上比计算机 B 慢 2 倍。那么您的算法在计算机 B 上的速度将是计算机 B 的两倍。尽管当您考虑算法的大输入值时，速度的两倍实际上几乎没有区别。

In big O notation也就是说，与 CO(n) = O(cn) = O(n) 相比，您将拥有类似 O(n) 的东西。算法的复杂度和大值的一般运行时间在计算机 A 和计算机 B 上大致相同。

如果您使用诸如大 O 表示法之类的东西来分析算法的运行时间，那么您将对该算法的实际工作原理有一个更好的了解。当您将复杂度为 O(logn) 的算法与复杂度为 O(n^2) 的算法进行比较时，计算机性能不会给您带来任何优势。

看一下 n 的一些数据值:

对于速度较慢的计算机，我假设每次操作需要 1 秒，对于速度较快的计算机，我假设每秒需要 2 次操作。我将比较速度较慢的计算机的较好算法和速度较快的计算机的较差算法。

对于 n = 10:

Algorithm 1: O(logn): 4 operations Slow computer: 4 seconds

Algorithm 2: O(n^2): 100 operations Fast computer: 50 seconds

对于 n = 100:

Algorithm 1: O(logn): 7 operations Slow computer: 7 seconds

Algorithm 2: O(n^2): 10,000 operations Fast computer: 1.4 hours

差别很大

对于 n = 1,000:

Algorithm 1: O(logn): 10 operations Slow computer: 10 seconds

Algorithm 2: O(n^2): 1,000,000 operations Fast computer: 5.8 days

巨大的差异

---

随着n的增加，差异越来越大。

现在，如果您尝试在较快/较慢的计算机上针对较大的输入大小运行这些算法中的每一个。没关系。放下 O(logn) 会更快。