1

以下函数的时间复杂度是多少？

    for(int i = 0; i < a.size; i++) {
        for(int j = i; j < a.size; i++) {
            //
        }
    }

我认为它小于大 O n^2 因为我们没有迭代第二个 for 循环中的所有元素。我相信时间复杂度是这样的：

n[ (n) + (n-1) + (n-2) + ... + (n-n) ]

但是当我解决这个公式时，结果是

n^2 - n + n^2 - 2n + n^2 - 3n + ... + n^2 - n^2

这似乎根本不正确。有人可以确切地告诉我如何解决这个问题，以及我错在哪里。

4

3 回答 3

5

那就是O(n^2)。如果您考虑迭代 where i = a.size() - 1，并且向后工作（i = a.size() - 2、i = a.size - 3等），您将看到以下迭代次数的总和 where n = a.size。

1 + 2 + 3 + 4 + ... + n

这个系列的总和是n(n+1)/2，也就是O(n^2)。请注意，大 O 表示法在应用于多项式函数时会忽略常数并采用最高的多项式幂。

于 2014-05-13T05:22:15.740 回答
2

它将运行：

1 + 2 + 3 + .. + n

哪个1/2 n(n+1)给我们O(n^2)

Big-O 表示法只会保留主导项，也会忽略常数

Big-O 仅用于比较使用相同复杂度分析标准的问题的相同变体的算法，当且仅当主要术语不同时。

如果主要项相同，则需要比较 Big-Theta 或时间复杂度，这将显示出细微的差异。

在此处输入图像描述

例子

一个

    for i = 1 .. n
      for j = i .. n
        ..

乙

    for i = 1 .. n
      for j = 1 .. n
        ..

我们有

Time(A) = 1/2 n(n+1) ~ O(n^2)

Time(B) = n^2 ~ O(n^2)

O(A) = O(B)

T(A) < T(B)

分析

可视化我们是如何得到的1 + 2 + 3 + .. n：

    for i = 1 .. n:
      print "(1 + "
      sum = 0
      for j = i .. n:
        sum++
      print sum") + "

将打印以下内容：

(1+n) + (1+(n-1)) + .. + (1+3) + (1+2) + (1+1) + (1+0)

n+1 + n + n-1 + .. + 3 + 2 + 1

1 + 2 + 3 + .. + n + n+1

1/2 n(n+1) + (n+1)

1/2 n^2 + 1/2 n + n + 1

1/2 n^2 + 3/2 n + 1
于 2014-05-13T06:00:49.770 回答
1

是的，迭代次数严格小于n^2，但仍然是Θ(n^2)。它最终会大于n^kany k<2，最终会小于n^kany k>2。

（作为旁注，计算机科学家经常说 big-O，而他们真正的意思是 big-theta (Θ)。从技术上讲，你见过的几乎所有算法都有O(n!)运行时间；所有合理的算法的运行时间都不会增长比 快 n!。但是说复杂性是O(n!)如果它也是 O(n log n)并不是真的有用，所以根据某种格莱斯格言，我们假设当有人说算法的复杂性是O(f(x))尽可能f(x)小的时候。）

于 2014-05-13T05:29:55.260 回答