此算法的复杂度(BigO)是多少? [英] What is the Complexity (BigO) of this Algorithm?

问题描述

我对Big-O知识还很陌生，我想知道算法的复杂性是什么.

我知道，如果语句和变量初始化为O(1)，则每次加法.

据我了解，第一个"i"循环将运行"n"次，第二个"j"循环将运行"n ^ 2"次.现在，第三个"k"循环就是我遇到的问题.

由于'j'的平均值将是'n'的一半，它是否运行'(n ^ 3)/2'次?

这是否意味着Big-O为O((n ^ 3)/2)?

解决方案

我们可以使用Sigma表示法来计算算法中最内部的基本操作的迭代次数， sum = sum + A[k]是基本操作.

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

让我们用Big-O表示法粗略地定义我们的意思:

f(n) = O(g(n))表示c · g(n)是f(n)上的上限.因此 存在一些常量c，使得f(n)始终为≤ c · g(n)， 对于足够大的n (即对于某些常量n0为n ≥ 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表示法时，我们将描述算法的渐近行为的上限，因此只有感兴趣的项才有意义(但是如何用常量来缩放).

I'm fairly new to the Big-O stuff and I'm wondering what's the complexity of the algorithm.

I understand that every addition, if statement and variable initialization is O(1).

From my understanding first 'i' loop will run 'n' times and the second 'j' loop will run 'n^2' times. Now, the third 'k' loop is where I'm having issues.

Is it running '(n^3)/2' times since the average value of 'j' will be half of 'n'?

Does it mean the Big-O is O((n^3)/2)?

解决方案

We can use Sigma notation to calculate the number of iterations of the inner-most basic operation of you algorithm, where we consider the sum = sum + A[k] to be a basic operation.

Now, how do we infer that T(n) is in O(n^3) in the last step, you ask?

Let's loosely define what we mean by Big-O notation:

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).

I.e., we want to find some (non-unique) set of positive constants c and n0 such that the following holds

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

for some function g(n), which will show that f(n) is in O(g(n)).

Now, in our case, f(n) = T(n) = (n^3 - n^2) / 2, and we have:

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                                           (++)

Now (++) is exactly (+) with c=1 (and choose n0 as, say, 1, n>n0=1), and hence, we have shown that f(n) = T(n) is in O(n^3).

---

From the somewhat formal derivation above it's apparent that any constants in function g(n) can just be extracted and included in the constant c in (+), hence you'll never (at least should not) see time complexity described as e.g. O((n^3)/2). When using Big-O notation, we're describing an upper bound on the asymptotic behaviour of the algorithm, hence only the dominant term is of interest (however not how this is scaled with constants).

这篇关于此算法的复杂度(BigO)是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！