什么时候值得使用更差的 Big-O 算法 [重复]

Question

如果可以选择不同时间复杂度的算法，那么什么时候选择“更差”的 Big-O 更值得，例如选择 O（n） 而不是 O（log n）。

Answer 1

任何渐近符号都描述了在输入达到一定大小(< code>n

例如，计算复杂度为2*n和3*n的两个算法将在同一个O（n）类中，而2*n^2算法将在O（n^2）中。现在，对于足够小的输入（本例中的n=1），2*n^2将比3*n算法更有效地执行。

这对于< code>O(n)相对于< code>O(log(n))(或任何其他)计算复杂性也是成立的。

Answer 2

复杂性并不能告诉你任何关于性能的信息，所以仅仅知道复杂性不足以决定一种方法是否比另一种更有价值。要知道在给定的情况下(例如，对于给定的问题大小)，一种方法是否比另一种方法更好，基准测试是一种方法。一旦您对不同的方法进行了基准测试，复杂性可以帮助您预测当问题变大时事情将如何扩展。

例如，了解算法的复杂性对图像处理非常有用：

想象一下，您有两个不同的过滤器，在2D图像上给出非常相似的结果，一个比另一个快于“普通”图像（例如一些百万像素）。如果将它们应用于 3D 图像，它们将如何表现（即，如果问题大小是千兆像素怎么办）？了解复杂性并拥有参考基准可以帮助您预测使用哪种过滤器“值得”使用，但最终......您仍将对这两种解决方案进行基准测试以确保。

Answer 3

大O意味着限制，当我们的代码处理有限数量的操作时，无限多的操作（因此大O是近似值）。比较两个时间复杂度：

t ~ 1e100 * N
t ~ N * N

对于真实世界的输入，第二种算法(具有更差的时间复杂度)是优选的，并且更快。