algorithm - 选择要使用的算法

Question

假设您有两个算法(A1 和 A2)

A1 = Omega(n)
A2 = O(n^2)

这些算法确定数字 n 是否为质数。 您应该选择哪一个？为什么？

并且在使用 A1 和 A2 对大量数据运行测试时也没有注意到运行时间的差异。这怎么可能？

Answer 1

these algorithms determines whether a number n is a prime number or not. Which one should you choose and why?

由于多种原因，所提供的算法规范信息量不够。

1. O(n^2) 和 Omega(n) 提供的信息不足以选择哪个具有更好的渐近复杂性。例如，您可以让 A1 在 Theta(n) 中运行，而 A2 在 Theta(n^2) 中运行，A1 将渐近地优于 A2。另一方面，您可以让 A1 在 Theta(n^3) 中运行，让 A2 在 Theta(log^3(n)) 中运行(which is the best known algorithm for testing primality of a number) .取决于其中哪一个是真正的复杂性 - 答案会有所不同

2. 此外，如果预期输入是 n 的小值，我们对预期输入一无所知 - 大 O 表示法(和大 Omega)信息量不大，因为他们只处理大值。

但是，第二个确实给了你一些上限，而第一个没有，所以这是一个额外的好处。虽然仍然不足以准确判断哪个更好。