该算法的复杂性（Big O）是多少？

Question

我对 Big-O 的东西还很陌生，我想知道算法的复杂性。

我理解每个加法、if 语句和变量初始化都是 O(1)。

根据我的理解，第一个 'i' 循环将运行 'n' 次，第二个 'j' 循环将运行 'n^2' 次。现在，第三个 'k' 循环是我遇到问题的地方。

是否运行宁'(n^3)/2'次因为'j'的平均值将是'n'的一半？

大O是不是O((n^3)/2)？

Answer 1

我们可以使用 Sigma 表示法来计算算法最内层 基本操作 的迭代次数，其中我们将 sum = sum + A[k] 视为基本操作操作。

现在，你问，我们如何推断 T(n) 在最后一步中 O(n^3)？

让我们粗略地定义大 O 表示法的含义：

f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for sufficiently large n (i.e. , n ≥ n0 for some constant n0).

即，我们想要找到一些（非唯一）正常数集 c 和 n0 使得以下成立

 |f(n)| ≤ c · |g(n)|, for some constant c>0                   (+)
                      for n sufficiently large (say, n>n0)

对于某些函数 g(n)，这将显示 f(n) 在 O(g(n)).

中

现在，在我们的例子中，f(n) = T(n) = (n^3 - n^2) / 2，我们有：

f(n) = 0.5·n^3 - 0.5·n^2

{ n > 0 } => f(n) = 0.5·n^3 - 0.5·n^2 ≤ 0.5·n^3 ≤ n^3

    => f(n) ≤ 1·n^3                                           (++)

现在 (++) 正好是 (+) 和 c=1（然后选择 n0 作为 1、n>n0=1），并且因此，我们已经证明 f(n) = T(n) 在 O(n^3).

中

从上面有点正式的推导可以看出，函数 g(n) 中的任何常量都可以提取并包含在 (+) 中的常量 c 中，因此您永远不会 (至少不应该）将时间复杂度描述为例如O((n^3)/2)。使用 Big-O 表示法时，我们描述的是算法 渐近行为 的上限，因此只有主导项是有意义的（但不是如何用常数缩放） .

该算法的复杂性（Big O）是多少？

What is the Complexity (BigO) of this Algorithm?

big-o

time-complexity