选择哪种算法使用 [英] Choosing which algorithm to use

问题描述

假设你有两种算法（A1​​和A2）

  A1 =欧米茄（N）
A2 =为O（n ^ 2）
 

这些算法确定一个数n是否是一个素数或没有。 哪一个你应该选择？为什么？

和还当运行试验在大量与在运行时间A1和A2没有差别悉。这怎么可能？

解决方案

  

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

的算法所提供的规范不是信息量不够的，有几个原因。

1. 为O（n ^ 2）和欧米茄（n）是不够的信息，以选择具有较好渐进的复杂性。例如，你可以有A1运行在的Theta（N），和A2 运行西塔（N ^ 2）和A1将是渐进比A2好。在另一方面，你可以有A1在运行西塔（N ^ 3），和A2 运行西塔（日志^ 3（N）） （这是最有名的算法一些的测试素性） 。根据其中的这些是真正的复杂性 - 的答案各不相同

2. 此外，我们不知道预期的输入任何东西，如果预期的投入是小的值 N - 大O符号（和大欧米茄）不是非常丰富，因为它们只处理较大的值。

不过，第二确实给你一些上限，而第一个没有，所以这是一个奖金。虽然仍不足以能够准确地知道哪个是更好的。

Suppose that you have two algorithms (A1 and A2)

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

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

and also when running test on a large number with A1 and A2 no difference in running time is noted. How is this possible?

解决方案

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

The provided specification of the algorithms is not informative enough, for several reasons.

1. O(n^2) and Omega(n) is not informative enough to chose which has better asymptotic complexity. For example, you can have A1 runs in Theta(n), and A2 runs in Theta(n^2), and A1 would be asymptotically better than A2. On the other hand, you could have A1 run in Theta(n^3), and A2 run in Theta(log^3(n)) (which is the best known algorithm for testing primality of a number). Depending on which of these is the true complexity - the answer will vary

2. In addition, we don't know anything about expected input, if the expected inputs are small values of n - big O notation (and big Omega) are not very informative, as they only handle large values.

However, the 2nd does give you some upper bound, while the first one does not, so that's a bonus. Though still not enough to be able to accurately tell which is better.

这篇关于选择哪种算法使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！