算法的大O复杂度

我想弄清楚算法的确切的大O值。我将提供一个例子：算法的大O复杂度

for (int i = 0; i < n; i++) // 2N + 2 
{ 
    for (int x = i; x < n; x++) // N * 2N + 2 ? 
    { 
     sum += i; // N 
    } 
} // Extra N?

所以，如果我打破一些的这个下来，INT I = 0会O（1）中，i < n为N + 1，I + +是N，乘内环由N：

2N + 2 + N（1 + N + 1 + N）= 2N^2 + 2N + 2N + 2 = 2N^2 + 4N + 2

添加的N为循环终止和总和常数，= 3N^2 + 5N + 2 ...

基本上，我不是100％确定如何计算确切 O表示法，我的猜测是O（3N^2 + 5N + 2）。

来源

2016-08-25 Awbelton

使用Big-O时，可以省略常量和所有非最高阶项。在这种情况下，O（3N^2 + 5N + 2）=> O（n^2）。这是因为随着n的增长，这些术语以n^2为主，变得非常微不足道。 – Clip

你的情况是'N'？ “int i = 0将是O（1），”---呃，不。大O分析不是当你在一堆中加入不同的东西时。 – zerkms

逻辑上，'i

你是什么意思？大O是一个渐近上界，所以它的定义并不确切。

由于O（N + 1）不正确，因此将i=0考虑为O（1）和i<n。相反，将外部循环看作n次执行，并且对于外部循环的每次迭代，内部循环最多执行n次。循环内的计算需要一定的时间（随着n变大，计算并不复杂）。所以你最终得到O（n * n * 1）= O（n^2），二次复杂度。

当询问“确切”时，您将运行内循环，从0到n，然后从1到n，然后从2到n，...，从（n-1）到n，每次做一个恒定的时间操作。所以你做n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2 = n^2/2 + n/2迭代。要从计算的确切数目到大O符号，省略常数和低位术语，最后以O（n^2）结尾（省略了1/2和+n/2和+n/2）。

来源

2016-08-25 03:27:53 user835611

-2

大O意味着最坏情况的复杂性。

而在这种情况下，最坏的情况只有在两个循环都会运行n个时间，即n * n时才会发生。

因此，复杂性是O（n2）。

来源

2016-08-26 06:18:29 Durgesh

大O并不一定意味着最坏情况下的复杂性。它是一个普遍的渐近界。您也可以将其应用于预期的运行时或任何其他功能。 – AEF

好友，小o是不紧的界限，大O是最坏的情况，但紧紧地绑定。但是，通常我们不使用小的o来表示最坏情况的复杂度。我们用Big O来说最坏的情况。 – Durgesh

这是不正确的。大O给任意函数提供了一个渐近上界。你可以用它来描述你想要的任何函数的行为。如果该函数描述“每个输入长度的最坏情况复杂度”或“每个输入长度的平均个案复杂度”，甚至“世界上每个人数消耗的全球苹果量”，则无关紧要。这是一个比你想像的更普遍的概念。 – AEF

算法的大O复杂度

回答

相关问题