java - 你会如何选择一种算法优于另一种算法的地方

Question

我正在尝试比较两种算法及其 Big Oh 效率。我试图找到一个算法比另一种算法更有效的 n 值。任何有用的例子或资源都会有很大的帮助。

Answer 1

您确实需要了解的不仅仅是算法的 BigO 复杂性，以便准确确定一种算法在什么时候变得比另一种更有效，假设它们具有不同的低阶项和常数，并且具有更差 BigO 特性的算法具有更好的低阶术语\常量。但通常近似值就足够了。

算法的运行时复杂度是处理输入规模不断扩大的问题时使用的工具。

经验性能分析是处理通常涉及小输入的高频、重复性问题时使用的工具*

(*) 什么构成小输入取决于所涉及算法的复杂性。例如，对于旅行商问题，大小为 5 的输入很小，而大小为 15 的输入很大。对于排序，20 个元素被认为是小元素，20000 个元素是大元素，2000000 个元素是大元素。