0

我已经为解决相同问题的两种算法提供了运行时函数。比方说——

对于第一个算法：T(n) = an + b（n中的线性）
对于第二个算法：T(n) = xn^2 + yn + z（n中的二次）

每本书都说时间线性优于二次，当然它适用于更大n（多大？）。我觉得 Big changes的定义基于常量a、b、x和。yz

您能否告诉我如何找到n我们应该何时从 algo2 切换到 algo1 的阈值，反之亦然（是否只能通过实验找到？）。如果有人能解释它是如何在专业软件开发组织中完成的，我将不胜感激。

如果不能，我希望我能够解释我的问题，请告诉我。

在此先感谢您的帮助。

PS - 该实现将使用 Java 并有望在各种平台上运行。我发现很难用数学方法估计常数、a、b和x。我们如何解决专业软件开发中的这一困境？yz

4

6 回答 6

5

我总是使用 O(n) ，对于较小的 n 它可能会更慢，但无论如何 n 很小。如果尝试为每个数据集选择最佳算法，代码中增加的复杂性将使调试和维护变得更加困难。

于 2012-07-13T08:26:00.873 回答
2

不可能在所有实际感兴趣的情况下估计固定因子。即使可以，除非您还可以预测输入的大小在未来将如何演变，否则它也无济于事。

除非其他因素也起作用（例如内存消耗），否则应该始终首选线性算法。如果实际性能不可接受，您可以寻找替代方案。

于 2012-07-13T08:26:39.840 回答
1

实验。我还遇到过一种情况，我们有代码可以在实例列表中查找特定实例。原始代码做了一个简单的循环，它运行了好几年。有一次，我们的一位客户记录了一个性能问题。在他的案例中，列表包含数千个实例，查找速度非常慢。

我的开发伙伴的解决方案是在列表中添加散列，这确实解决了客户的问题。但是，现在其他客户开始抱怨，因为他们突然遇到了性能问题。似乎在大多数情况下，列表只包含几个（大约 10 个）条目，并且散列比仅循环列表要慢得多。

最终的解决方案是测量两种备选方案（循环与散列）的时间，并确定循环变得比散列慢的点。在我们的例子中，这大约是 70。所以我们改变了算法：

  • 如果列表包含少于 70 个项目，我们循环
  • 如果列表包含超过 70 个项目，我们会散列

解决方案可能与您的情况类似。

于 2012-07-17T06:48:51.977 回答
1

只需使用预期的输入大小来分析代码，如果您还添加最坏情况的输入，那就更好了。不要浪费时间求解方程，这可能一开始就无法推导出来。

通常，从 n = 10000 的大小，您可以预期 O(n 2 ) 比 O(n) 慢得多。明显慢意味着任何人都可以注意到它更慢。根据算法的复杂性，您可能会注意到较小 n 处的差异。

重点是：根据时间复杂度来判断算法可以让我们忽略一些算法，这些算法对于最大输入大小的任何输入来说显然太慢了。但是，根据输入数据的域，某些具有较高复杂度的算法实际上会优于其他具有较低时间复杂度的算法。

于 2012-07-13T08:24:27.787 回答
1

你问的是数学问题，而不是编程问题。

注意我会假设 x 是积极的......

你需要知道什么时候

an+b < xn^2 + yn + z

IE

0 < xn^2 + (y-a)n + (z-b)

您可以将其插入求解二次方程的标准方程http://en.wikipedia.org/wiki/Quadratic_equation#Quadratic_formula

并取较大的 0，然后您知道对于所有大于此的值（作为 x 正数）O(n^2) 更大。

你最终得到一个包含 x、y、a、z 和 b 的可怕方程，我非常怀疑它对你有什么用处。

于 2012-07-13T08:32:54.940 回答
0

当我们为大规模目的编写算法时，我们希望它在较大的“n”中表现良好。在您的情况下，取决于a, b, x, y and z，第二种算法可能会表现得更好，尽管它是二次的。但无论 的值是什么，都会有一些（比如说）a, b, x, y and z下限，超过该下限，第一个算法（线性算法）总是比第二个更快。nn0

If f(n) = O(g(n))
then it means for some value of n >= n0 (constant)
f(n) <= c1*g(n)

So
if g(n) = n,
then f(n) = O(n)

因此，根据您的使用情况选择算法n

于 2012-07-17T06:42:01.293 回答