13

两种算法说 A 和 B 是为了解决同一个问题而编写的。算法 A 是 O(n)。算法 B 是 (n^2)。您希望算法 A 能更好地工作。

但是，当您运行同一台机器的特定示例时，算法 B 运行得更快。给出理由来解释这样的事情是如何发生的？

4

5 回答 5

34

例如，算法 A 可以及时运行，10000000*n即O(n).
如果算法 B 正在其中运行n*n，则O(n^2)A 对于每个 都会变慢n < 10000000。

O(n), O(n^2)是描述行为的渐近运行时n->infinity

编辑 - 示例

假设你有以下两个函数： 

boolean flag;

void algoA(int n) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 1000000; j++)
      flag = !flag;

void algoB(int n) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      flag = !flag;

algoA有n*1000000标志翻转操作，所以它是O(n)，而algoB有n^2标志翻转操作，所以它是O(n^2)。

只要解决不等式1000000n > n^2，你就会得到它，因为n < 1000000它成立。也就是说，该O(n)方法会更慢。

于 2013-04-14T08:16:48.553 回答
4

Big-O-notation 没有说明速度本身，只说明当你改变速度时速度将如何变化n。

如果两种算法在一次迭代中花费相同的时间，@Itay 的示例也是正确的。

于 2013-04-14T08:18:01.453 回答
4

了解算法将有助于给出更准确的答案。

但对于一般情况，我可以想到一些相关因素：

  • 硬件相关

    例如，如果较慢的算法很好地利用了缓存和局部性或类似的低级机制（参见 Quicksort 与其他理论上更快的排序算法相比的性能）。也值得阅读有关timsort的内容，例如，使用“高效”算法将问题分解为较小的输入集，并在这些集上使用“更简单”且理论上“更高复杂度”的算法，因为它更快。

  • 输入集的属性

    例如，如果输入大小很小，则效率不会在测试中通过；另外，例如再次排序，如果输入大部分是预先排序的而不是完全随机的，你会看到不同的结果。在这种类型的测试中应该使用许多不同的输入以获得准确的结果。仅使用一个示例是不够的，因为可以将输入设计为支持一种算法而不是另一种算法。

  • 任一算法的具体实现

    例如，从算法的理论描述到实现还有很长的路要走；数据结构、递归、内存管理等使用不当会严重影响性能

于 2013-04-14T08:20:04.013 回答
3

虽然到目前为止所有答案似乎都是正确的……但在 CS 课程的背景下，没有一个人觉得真正“正确”。在计算复杂性课程中，您希望精确并使用定义。我将概述这个问题和一般计算复杂性的许多细微差别。最后，我们将总结为什么 Itay 的顶部解决方案可能是您应该编写的。我对 Itay 解决方案的主要问题是它缺少定义，而这些定义是为 CS 类编写良好证明的关键。请注意，我的定义可能与您的班级略有不同，因此请随意替换您想要的任何内容。

当我们说“一个算法是O(n)”时，我们实际上是指“这个算法在集合中O(n)”。并且该集合O(n)包含所有算法，其最坏情况渐近复杂度 f(n)具有f(n) <= c*n + c_0对于某个常数c和c_0where的属性c, c_0 > 0。

现在我们要证明你的主张。首先，您陈述问题的方式，它有一个简单的解决方案。那是因为我们的渐近界是“最坏情况”。对于许多“慢”算法，有一些输入运行得非常快。例如，如果输入已经排序，则插入排序是线性的！因此，使用插入排序 ( O(n)) 和合并排序 ( O(nlog(n))) 并注意如果传入排序数组，插入排序会运行得更快！砰，证明完成。

但是我假设您的考试更像是“说明为什么在最坏的情况下线性算法可能比二次算法运行得更快”。正如亚历克斯上面提到的，这是一个开放式问题。问题的症结在于运行时分析假设某些操作是O(1)（例如，对于某些问题，您可能会假设乘法O(1)即使对于大数而言它变得二次方慢（有人可能会争辩说，给定问题的数字是有界的） 100 位，所以它仍然是“恒定时间”））。由于您的课程可能专门关注计算复杂性，因此他们可能希望您忽略这个问题。所以我们将证明这个主张，假设我们的O(1)假设是正确的，因此没有像“缓存使这个算法比另一个更快”这样的细节。

所以现在我们有一个运行在f(n)which is中的O(n)算法和一些在 which is 中运行的其他g(n)算法O(n^2)。我们想使用上面的定义来表明对于某些n我们可以拥有g(n) < f(n). 诀窍是我们的假设并没有固定c, c_0, c', c_0'. 正如 Itay 所提到的，我们可以为这些常数选择值，例如g(n) < f(n)对于 many n。其余的证明是他在上面写的（例如，让c, c_0是常数f(n)，说它们都是 100，而c', c_0'是常数g(n)，它们都是 1。然后g(n) < f(n) => n + 1 < 100n^2 + 100 => 100n^2 - n + 99 > 0 => (factor to get actual bounds for n)）

于 2013-04-14T09:16:18.623 回答
1

这取决于不同的场景。有 3 种类型的场景 1.Best、2.Average、3.Worst。如果您知道排序技术，也会发生同样的事情。有关更多信息，请参阅以下链接：

http://en.wikipedia.org/wiki/Sorting_algorithm

如果我错了，请纠正我。

于 2013-04-14T08:29:48.150 回答