大 O 符号估计

Question

不确定这里是否是此类问题的正确位置，但在这里。给定以下代码，有多少个基本操作，每个操作执行多少次。这个运行时间的大 O 表示法是什么。如果重要的话，这是在 MATLAB 中。

total = 0;

for i = 1:n
    for j = 1:n
        total = total + j;
    end
end

我的想法是，对于每个 n，j = 1:n 循环运行一次。在 j = 1:n 循环中有 n 次计算。所以对于 j = 1:n 循环它的 n^2。这在 i = 1:n 循环中运行 n 次，因此计算总量为 n^3，大 O 表示为 O(N^3)。这是正确的吗？

Answer 1

您的分析是正确的，但您将成本高估了 n 倍。特别是，看这里：

Within the j = 1:n loop there are n calculations. So for the j = 1:n loop its n^2.

你说得对，j = 1:n 循环进行了 n 次计算，但是循环的每次迭代只进行了 1 次计算。由于循环运行了 n 次，所以完成的工作是 O(n)，而不是 O(n²)。如果您随后从该点开始重复其余的分析，您最终会得到完成的总功为 Θ(n²)，这是一个比之前更严格的界限。

请注意 - 您实际上可以大大加快速度。请注意，内部循环将 1 + 2 + 3 + ... + n 添加到总数中。我们知道 1 + 2 + 3 + ... + n = n(n+1)/2，所以可以将代码重写为

total = 0;

for i = 1:n
     total = total + n * (n + 1) / 2;
end

但是请注意，现在您只是添加了 n * (n + 1) / 2 的副本，因此您可以将其重写为

total = n * n * (n + 1) / 2

整个事情需要时间 O(1)。

Answer 2

简短的回答是：

O(n^2)

长（和简化）答案是：

大 "O" 指的是算法的复杂性（在本例中是您的代码）。您的问题询问执行了 "how many" 循环或操作，但是 "O" 表示法给出了算法复杂性的相对概念，因此不是绝对数量。这完全是不切实际的，O 表示法的想法是概括复杂性的度量，以便算法可以相对于其他算法进行比较，而不必太担心执行了多少赋值、循环等。

也就是说，有关于如何计算算法复杂性的具体指南。一般：

循环的复杂度为 O("n")，无论它们执行多少次迭代（记住，这是一个抽象度量）。
赋值、加法等操作通常近似于 O(1)（复杂度为 1），因为执行它们所花费的时间可以忽略不计。

if then else操作是有具体规则的，但是这样会比较复杂，请大家看一下introduction material on performing algorithm complexity analysis。

此外，请注意，"n" 不是您代码中使用的那个，它是一种特殊符号，用于表示 "generic" 线性复杂度。

衡量算法的复杂性是一种递归操作。您从基本操作开始，然后向上移动到循环等。因此，这里有一个详细信息（我故意详细说明太多，以便您了解它是如何工作的，但实际上您不必深入到那个级别的细节):

您从第一条指令开始：

O(total = 0;) = O(1)

因为这是作业。

然后：

O(total = total + j;) = O(total + j) + O(total = x)

其中 x 是 total + j 的结果。

                      = O(1) + O(1)

这些是基本操作，因此它们的复杂度为 1。

                      = O(1)

因为 "O" 是一个 "greatness" 指标，它将任何常数之和视为 1。

现在进入循环：

O(
    for i = 1:n // O(n)
        for j = 1:n // O(n)
            total = total + j; // O(1)
        end
    end
)
=
O(
    n * ( 
        n * (
            1
        )
)
= O(n * n * 1)
= O(n^2)

如果连续有两个循环（for ... ; for .... ;），复杂度不会是 O(2n)，而是 O(n)，因为 O 再次概括。

希望对您有所帮助:)

大 O 符号估计

Big O notation estimate

performance

big-o

benchmarking