algorithm - 最高阶的增长函数是最慢的吗？

Question

高阶增长函数是否耗时最长？那么，O(n²) 比 (2ⁿ) 花费的时间更少？

当 N 很大时，最高阶的增长函数实际运行时间是否最长？

Answer 1

大 O 表示法的思想是表达算法复杂度的最坏情况。例如，一个使用循环的函数可能被描述为 O(n)，即使它包含多个 O(1) 语句，因为它可能必须在 n 个项目上运行整个循环。

n 是您正在测量的算法的输入数。以 n 表示的大 O 告诉您随着输入数量越来越大，该算法将如何执行。这可能意味着它将花费更多时间来执行，或者某些东西将花费更多空间来存储。如果您注意到您的算法具有较高的 Big-O(如 O(2^n) 或 O(n!))，您应该考虑一种可扩展性更好的替代实现(假设 n 会变大——如果 n 总是很小)没关系)。这里的关键要点是，Big-O 可用于向您展示两种算法中哪一种可以更好地扩展，或者可能只是一种算法会成为性能严重瓶颈的输入大小。

这是一个比较多个多项式的示例图像，可以让您了解它们在 Big-O 方面的增长率。增长时间是随着 n 接近无穷大，用图形术语来说就是随着 x 变大函数沿 y 轴向上弯曲的急剧程度。

如果不清楚，这里的x轴是你的n，y轴是花费的时间。您可以从中看出，例如，O(n^2) 比 O(n) 消耗时间(或空间，或其他)要快得多。如果你绘制更多的图形并缩小，你会看到不可思议的差异，比如说，O(2^n) 和 O(n^3)。

尝试一个具体的例子

使用您比较两个大小为 20 的字符串数组的示例，假设我们这样做(伪代码，因为它与语言无关):

for each needle in string_array_1:
    for each haystack in string_array_2:
        if needle == haystack:
            print 'Found!'
            break

这是 O(n^2)。在最坏的情况下，它必须完全运行完第二个循环(以防找不到匹配项)，这发生在第一个循环的每次迭代上。对于两个大小为 20 的数组，这是 400 次总迭代。如果每个数组都被仅一个字符串增加到大小 21，则最坏情况 中的迭代总数会增长到441!显然，这可能很快就会失控。如果我们有包含 1000 个或更多成员的数组怎么办？请注意，此处将 n 视为 20 并不正确，因为数组的大小可能不同。 n 是一种抽象，可帮助您了解在越来越多的负载下情况会变得多么糟糕。即使 string_array_1 的大小为 20 而 string_array_2 的大小为 10(或 30，或 5!)，这仍然是 O(n^2)。