有人可以评估一下这个函数的时间复杂度吗

Question

function    (n)
input : an  integer n
r ← 0
for i = 1 to n  //runs n times
    for j = i   + 1 to n     // runs n^2 times
           for k = i + j − 1 to n   //runs n^3 times
                r ← r + 1
return r

我的答案是 O(n^3)，但是当我尝试使用 sigma 表示法找到它时，结果总是 O(n^2)。

原问题：

以下算法返回什么值？ 它的基本操作是什么？ 如何
基本操作执行了多少次？ 给出最坏情况下的运行时间
使用 Big Oh 表示法的算法。

Answer 1

tldr： 算法在

O(n^3)

。

---

为什么？

计算

r <- r + 1

执行的频率。

如果有帮助，请用某种语言实现它并执行它以获得更好的感觉。以 Java 为例：

int n = 10;

int r = 0;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        for (int k = i + j - 1; k <= n; k++) {
            r++;
        }
    }
}

---

简介

外层循环生成

n

次迭代，正确。第二个循环将生成

n - 1, n - 2, n - 3, n - 4, ...

代。

最里面的循环取决于

i

、

j

和

n

。

例如，修复

i = 1

并让

j

从

n - 1

运行到

1

。您将得到

k

1 + (n - 1)

到

n

，这根本不是运行。然后从

1 + (n - 2)

到

n

，即

2

次运行，最多

n

次运行。

所以有了

i = 1

，你就会得到

k = 2, 3, 4, ..., n

。然后

i = 2

，你就会得到

k = 4, ..., n + (n + 1)

。如此重复并求和，直到

i = n

只产生

k = (n+(n-2))

，总共：

i = 1 -> k = 2, 3, 4, 5, 6, ..., n
i = 2 -> k =       4, 5, 6, ..., n, (n+1)
i = 3 -> k =             6, ..., n, (n+1), (n+2)
  .
  .
  .
i = n -> k =                  (n+(n-2))

对于带有

n = 10

的示例，这是：

2, 3, 4, 5, 6, 7, 8, 9, 10 
      4, 5, 6, 7, 8, 9, 10, 11
            6, 7, 8, 9, 10, 11, 12
                  8, 9, 10, 11, 12, 13
                        10, 11, 12, 13, 14
                                12, 13, 14, 15
                                        14, 15, 16
                                                16, 17
                                                        18

对于

k

。

---

k

的值

现在请注意，循环仅执行到

k <= n

。因此，您可以丢弃所有高于

k

的

n

值，并计算剩余值的迭代次数。

2, 3, 4, 5, 6, 7, 8, 9, 10| 
      4, 5, 6, 7, 8, 9, 10|, 11
            6, 7, 8, 9, 10|, 11, 12
                  8, 9, 10|, 11, 12, 13
                        10|, 11, 12, 13, 14
                          |     12, 13, 14, 15
                          |             14, 15, 16
                          |                    16, 17
                          |                           18

---

总跑数

因此，其中每一个都是

k

的值，它将生成

(n + 1) - k

许多运行。所以这样做你会得到：

9, 8, 7, 6, 5, 4, 3, 2, 1
      7, 6, 5, 4, 3, 2, 1
            5, 4, 3, 2, 1
                  3, 2, 1
                        1

将这些相加，您最终得到总运行次数：

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
      + 7 + 6 + 5 + 4 + 3 + 2 + 1
              + 5 + 4 + 3 + 2 + 1
                      + 3 + 2 + 1
                              + 1

这会产生

r = 95

。

---

公式与证明

确切的公式是：

sum_{i = 1}^{n - 1} ceil((n - i) / 2) * i

如果你删除

ceil

（它不会影响复杂性），你可以将其简化为

n^3 / 12 - n / 12

现在您可以轻松地看到并证明这是在

O(n^3)

中。

Answer 2

答案是.. 将会是

O(n^3)