主页 / 问题 / 1398000
Accepted
Дядя Фёдор
Asked:2022-09-07 21:43:48 +0000 UTC2022-09-07 21:43:48 +0000 UTC

为什么在 O(n) 中运行的算法并不总是比在 O(n^2) 中运行的第二个算法快？

  • 772

停止对这个问题的测试。我不知道出了什么问题，我确定我回答正确

问题是这样的

第一个算法在 O(n) 中运行，第二个在 O(n^2) 中运行。选择正确的说法

1 - 对于足够小的 n，第二个将运行得更快
2 - 第一个总是比第二个快
3 - 第二个总是比第一个快
4 - 对于足够大的 n，第一个将运行得更快

我选择第一个总是比第二个快

有一个循环，一个循环中也有一个循环。所以第一个总是更快。为什么我错了？

алгоритм

3 个回答

    • 1 -如果 n 足够小，第二个将运行得更快- 和之间的n差异足够小O(n)，O(n^2)将是最小的，并且无法确定哪种算法运行得更快
    • 2 -第一个总是比第二个快- 这并不总是，但见上文
    • 3 -第二个总是比第一个快- 不，当然
    • 4 -对于足够大的 n，第一个会更快- 但这与差异的本质非常相似，O(n)并且O(n^2)
    • 2
  2. Best Answer

    让我先告诉你为什么你错了。

    第一个总是比第二个快

    让第一个算法的步数对输入数据大小的依赖性由公式表示f(n)=3*n，对于第二个 - g(n)=n^2.

    请注意，对于所有人n<3 f(n) > g(n)来说，这至少可以从图表中看出：

    图表

    那些。第二种算法将采取更少的步骤，这意味着当数据很少时它会更快地工作（n<3）。同时，第一种算法O(n)的复杂度为 ，第二种算法的复杂度为O(n^2)。这是一个反例，它说明了为什么具有复杂性的算法O(n)总是比具有复杂性的算法更快的说法是错误的O(n^2)。

    可能，有必要解释算法具有复杂性意味着什么，O(n)或者，O(n^2)在一般情况下O(f(n))，f(n)某个函数在哪里。

    一般定义是：

    该算法具有复杂性O(f(n))，如果有这样的数字，C并且N该算法的步数（由公式定义g(n)）满足每个条件n>N: g(n) <= C*f(n)

    我将从第一个算法的示例开始，其中步数由公式确定k(n)=3*n。如果我们取C=3 и N=1，那么我们得到任何，这意味着，n>1根据3*n <= 3*n定义，算法具有复杂性O(n)。这里f(n)=n和g(n)=3*n。

    • 2

  3. 我们可以从纯理论的角度正式地接近，而不涉及新实体- n <= n^2：

    1 - “对于足够小的 n，第二个会跑得更快” - 显然不是，因为 除了复杂性之外，我们没有任何其他有助于提高速度的组件的信息。
    2 - “第一个总是比第二个快” -不，对于 n=1，两者都是相同的。
    3 - “第二个总是比第一个快” - 显然不是。
    4 - “对于足够大的 n，第一个会跑得更快” - 显然是的。

    • 1

相关问题