这种算法的 Big O 是什么？

Question

如果您有这样的代码，大 O 会是什么？我不确定 if 语句如何影响大 O。

n = some arbitrary number
for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
    if(i <= j)
      for(k = i; k <= j; k++)
        //do some simple operation
        y = x+1
    else
        //do some simple operation
        y = y+1

我不考虑编译器优化。我知道这是 O(n^2) 和 O(n^3) 之间的某个地方，但我不确定，因为 if 语句并不总是执行最内层的循环。

Answer 1

这是 O(N^3)。

证明：http://www.wolframalpha.com/input/?i=sum+sum+%28j+-+i+%2B+1%29%2C+j+%3D+i+to+n+-+1%2C+i+%3D+0+to+n+-+1

最后一个循环运行 (j - i + 1) 次。

如何手动找到这笔金额？这不是火箭数学。

尝试阅读 https://en.wikipedia.org/wiki/Telescoping_series

只是为了节省时间，为此目的使用 wolframalpha 更容易。

Answer 2

O(N * N * N) 我们可以说是 O(N^3)

第一次循环发生N次。第二个循环发生 N 次。那些相乘得到 O(N^2)

在所有可能的 N^2 循环中，第三个循环将运行大约一半的时间，即 O(N/2) 等同于 O(N)。

这就是你如何得到 O(N * N * N) 或 O(N^3)

Answer 3

事实上，您可以（几乎准确地）计算您执行了多少次操作：

i: 0 到 n-1 = N 次操作

x

j: 0 到 n-1 = N 次操作

x

仅当i<=j，从i到j，或者另一个任务O(1)

other 任务给你 NxN 操作，然后 O(NxN)

也就是说，如果你反转

对于每个 j（0 到 n-1）：N 个操作

那么对于从0到j的每一个i，你都做一个从i到j的操作，即j-i+1

和每0到j次操作完全一样。然后你有 (j+1)x(j+2)/2 个操作。

最后，你得到从 0 到 N 的 Sum (j+1)x(j+2)/2 即

1/2 ((N+1)x(N+2)/2 + (N+1)^3/3+(N+1)^2/2+(N +1)/6) 操作，所以 O(N^3)

也许，我忘记了一些+/-1

Answer 4

您可以使用 Sigma 符号分析您的算法：

由此可见，时间复杂度将取决于立方 n 项，因此您的算法在 O(n^3).

中

这种算法的 Big O 是什么？

What is the Big O of such an algorithm?

algorithm

big-o