6 
int num = n/4;
for (int i = 1; i <= num; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= n; k++) {
            int count = 1;
        }
    }
}

根据我读过的书，这段代码应该是O((n^3)/4)。但显然不是。要找到嵌套循环的 Big-O，你应该乘以界限吗？所以这个应该是 num *n *n 或 n/4 *n *n。

4

4 回答 4

15

O((n^3)/4)就大 O 表示法而言没有意义，因为它旨在将复杂性衡量为参数的比率。除以 4 没有任何效果，因为这会改变比率的值，但不会改变其性质。

所有这些都是等价的：

O(n^3)
O(n^3/4)
O(n^3*1e6)

其他术语仅在包含术语时才有意义n，例如：

O(n^3 / log(n))
O(n^3 * 10^n)

正如 Anthony Kanago 正确指出的那样，惯例是：

  • 只保留总和增长率最高的项：O(n^2+n) = O(n^2).
  • 摆脱产品的常量：O(n^2/4) = O(n^2).

顺便说一句，我并不总是在所有情况下都同意第一条规则。这是决定函数最大增长率的好规则，但对于算法比较(a)之类的事情，您可以智能地对输入参数设置限制，类似O(n^4+n^3+n^2+n)的事情明显比O(n^4).

在这种情况下，应包括任何依赖于输入参数的术语。事实上，即使是常数项在那里也可能有用。例如，比较一下O(n+1e100)-O(n^2)后者将在相当长一段时间内优于前者，直到n变得足够大以对常数项产生影响。

(a)当然，有些人会说不应该以这种方式使用它，但实用主义通常会在现实世界中克服教条主义 :-)

于 2009-04-20T04:57:07.553 回答
1

从http://en.wikipedia.org/wiki/Big_O_notation您可以看到像 1/4 这样的常量对于确定 Big-O 表示法没有任何作用。唯一有趣的事实是它是 n^3，因此是 O(N^3)。

于 2009-04-20T05:02:54.623 回答
0

形式上，时间复杂度可以如下推导：

在此处输入图像描述

于 2014-03-17T21:54:07.180 回答
-1

一个小技术。大 O 表示法旨在根据输入的“大小”而不是数值来描述复杂性。如果您的输入是一个数字，那么输入的大小就是您的数字的位数。唉，您的算法是 O(2^N^3) ，其中 N 是位数。

有关此主题的更多信息

于 2009-04-20T05:41:29.443 回答