我对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)是多少?
发布评论