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

两种算法在 O(n) 中运行

  • 772

我在这个问题的测试中被切断了，但我无法深入了解它。

问题是这样的

这两种算法在 O(n) 时间内运行。选择正确的说法

1 - 两种算法运行的秒数相同 2 - 第一种算法总是运行得更快，或者第二种算法运行得更快 3 - 有时第一种算法运行得更快，有时第二种算法运行得更快，有时相同

我回答了 1 - 结果是错误的

该条件没有说明任何有关设备或过程的信息。

O(n) 是相同的线性渐近线。在所有元素都循环通过之前，什么都不会改变。

алгоритм

2 个回答

  1. Best Answer

    线性复杂度意味着算法运行的时间大约等于CN. 两种不同算法的运行时间大约为C1 * N, C2 * N。C1并且C2是取决于算法和设备的正常数。

    答案1不合适：如果C1它们C2明显不同，运行时间也会不同。

    如果和近似相等，则答案2不合适，那么您不能说一种算法比另一种算法快。C1С2

    答案3也不起作用。相反，它适合，但前提是C1并且С2近似相等。然后算法将在大约相同的时间内工作。并且由于“约”，有可能“有时第一个可以更快，有时第二个，有时相同”。

    什么是在问题的作者的头是不是说。也许第三个答案是有意义的——它单独包含“可能”这个词。

    • 3

  2. 我支持第三种选择。

    • 1 -两种算法运行的秒数相同- 我们没有这样的保证，O(n)它只保证两种算法的运行时间线性依赖于n，但不保证这个时间相同
    • 2 -第一个算法总是运行得更快，或者第二个 - 再次，O(n)不保证时间是特定的，也没有说明要乘以的系数，n算法的运行时间可能取决于数据，什么都没有防止第一个算法工作得更快，但在其他一些算法上，虽然它们仍然会O(n)
    • 3 -有时第一个可以更快地工作，有时第二个可以更快，有时相同- 但此声明再次没有施加任何限制，顺便说一句，这对任何人都可能是真的O，如果n什么都没说，我押注这个选项。现在，如果说随着增加，n其中一种算法会比另一种更快，那么可以说O这些算法应该有不同的值（例如，O(n)和O(n^2)）。
    • 0

相关问题