在编程时，您经常需要为小任务选择一种算法。例如，如果您需要按名称选择一个帐户，可能会想到一堆算法。例如，对数组进行线性搜索或添加哈希图以在恒定时间内按名称查找。你应该选择哪一个？
研究表明，尽管复杂性更差，但更简单的算法可以在小型数据集上执行得更好。例如，冒泡排序是用于对小型数组进行排序的最快算法之一，而线性搜索甚至可以在计算中等复杂散列所需的时间内搜索数百个整数。
那么你选择什么算法呢？如果您知道您的数据通常很小，那么选择其中一种更简单的算法可能很诱人。大多数用户可能登录到一个帐户，很少有人会超过十个。因此，针对少量帐户进行优化对于几乎（如果不是全部）用户来说会更快，并且可能更易于实施。
我的默认建议是选择时间和空间复杂度低于二次方的最简单算法。每种情况都不同，但除非我有充分的例外理由，否则我会坚持这条规则。
原因很简单：
- 大多数代码对性能不敏感。不要花太多时间推测性能，默认情况下就可以了。由于特定的性能或架构问题，缓慢的应用程序通常很慢，而不是由于缺乏对每一行代码中微小细节的关注。
- 线性性能扩展是可以理解的，并且只是适度痛苦。用户不喜欢看到运行缓慢的软件，但他们明白拥有两倍的数据会导致速度加倍。性能也会逐渐降低，这有助于在您进行修复时容忍它。
- 对于大多数用例，在所有情况下都具有良好的性能比在简单情况下具有出色的性能更为重要。如果您的软件通常是高性能的，那么简单案例的速度已经可以接受，进一步优化它们对用户几乎没有好处。另一方面，复杂的案例已经将用户的耐心推到了极限，最好避免进一步放慢速度。
- 正常用例中的缓慢性能很可能会被开发人员注意到并迅速修复。分析将有助于针对热点进行优化工作。极端情况不太可能受到开发人员和大多数用户的影响，因此可能会持续更长时间，从而伤害少数人。
我真的很喜欢Bruce Dawson的这句话：
O(n 2 ) 是糟糕扩展算法的最佳点：快到足以使其投入生产，但又慢到足以让事情一旦到达那里就倒下
如果您经常将二次算法放入代码中，那么当用户将其推入您期望“始终很小”的维度时，他们会看到它下降。
记住来自Accidentally Quadratic博客的这个观察结果也很重要。
然而，线性的特性在组合下并不封闭。如果多次线性地进行线性运算，就会得到二次！
即使你总是选择次二次算法，组合也可能不是。所以你应该从整体上考虑系统的复杂性。在列表中查找帐户的线性搜索对于我的规则来说已经足够快了，但是如果您对每个帐户都这样做，那么您的系统总体复杂度为 O(n 2 )，我建议对其进行优化。
例子
作为一个具体的例子。要制作独特元素的列表，我想到了两个函数。第一个是 O(n 2 ) 算法，它执行简单的操作，即在添加元素之前检查每个元素是否在输出列表中。
fn unique < 'a > ( names : & [ & 'a str ]) -> Vec <& 'a str > { let mut result = Vec :: new (); for name in names { if ! result .contains ( name ) { result .push ( * name ); } } return result }
但是，我建议不要使用此功能，除非您确定输入永远不会很大。相反，我更愿意编写这个 O(n) 算法。
pub fn unique < 'a > ( names : & [ & 'a str ]) -> Vec <& 'a str > { let mut result = Vec :: new (); let mut seen = std :: collections :: HashSet :: new (); for name in names { if seen .insert ( name ) { result .push ( * name ); } } return result }
这稍微复杂一些，但这对我们期望的小数据集有伤害吗？是的，但这可能并不重要。算法在大约 60 个元素处交叉，此时运行时间小于 2µs。在最坏的情况下，线性版本在 30 个元素时将花费您大约 600ns。在 99.9% 的情况下，这并不重要。
Gnuplot 由 GNUPLOT 5.4 补丁级别 6010020030040050060070010203040506070Slowdown in Number of Elements$data
如果此功能确实出现在您的配置文件中，则很容易添加长度检查以选择数据大小的最佳算法。通过这种方式，您可以两全其美，在小型数据集上表现出色，但线性增长。但是，我认为对于大多数代码而言，这种复杂性不值得。我默认使用简单的次二次算法，然后分析我的代码并在重要的地方使用它。