理解大O符号

Question

给定以下代码，3.的复杂度是什么？ 我如何用以下复杂度表示简单算法？

O(n²+n)
O(n²+2n)
O(logn) O(nlogn)

注：复杂度指算法执行所需时间或空间资源与问题规模的增长关系。

var collection = new[] {1,2,3};
var collection2 = new[] {1,2,3};

//1.
//On
foreach(var i in c1)
{
}

//2.
//On²
foreach(var i in c1)
{
  foreach(var j in c1)
  {
  }
}

//3.
//O(nⁿ⁺ᵒ)?
foreach(var i in c1)
{
  foreach(var j in c2)
  {
  }
}

- Ben Aston

Answer 1

如果两个集合的大小相同，则3为O(n*m)或O(n^2)。

O(n^2+n)是无意义的，因为n小于n^2。只需写O(n^2)。

大多数像比较排序这样的算法运行时间为O(n*log(n))。如果您不知道任何算法，请查看维基百科。

二分搜索的时间复杂度为O(log(n))。

- Mark Byers

---

感谢。对于相同大小的集合，给定 O(n*m) = O(n^2)，如果一个集合的大小是另一个集合的一半，那么结果复杂度是什么？ - Ben Aston

澄清一下，如果预计这两个集合的大小成比例，那么我会说该算法的时间复杂度为n平方。否则，O(n*m)更为适当。 - Amish Programmer

@Ben Aston：你可以忽略O(n)表示法中的系数。如果m = n/2，那么O(n*m) = O(n^2/2) = O(n^2)。 - Mark Byers

John，你错了。如果大小为n和n/2，则复杂度为O(n^2)。 - shura

Answer 2

外部的foreach循环将执行n = |c1|次（其中| x |是c1的大小），而内部的foreach循环将执行m = |c2|次。总共执行了O(n * m)次。

---

如何表示具有以下复杂性的简单算法？

• O(n²+n)

这与O(n ^ 2)相同。需要O(n ^ 2)时间的例子是，在派对上与其他人交杯酒，假设每次交杯酒都只有两个人，并且一次只有一个人干杯。

• O(n²+2n)

与上面的例子相同；O(n ^ 2)项占主导地位。另一个O(n ^ 2)的例子是在长度为n的正方形花园中种树，假设每棵树的种植时间是恒定的，并且一旦您种植了一棵树，其他树就会被排除在其附近。

• O(logn)

通过重复选择您需要搜索的页面区域的中点来查找字典中的单词是O(logn)的例子。（换句话说，是二分搜索。）

• O(nlogn)

使用上述算法，但现在您必须在字典中找到每个单词。

- John Feminella

---

这是一个非常棒的解释。尽管只有一行，但你对O(n log n)的解释真的很清晰易懂。 - Mike B

Answer 3

没有O(n²+n)或者O(n^2 + 2n)这样的复杂度。忽略算法复杂度的大部分数学基础，至少你需要知道它是“渐近的”。当N趋向于无穷大时，n^2 + n的值被n ^ 2项所主导，因此n^2 + n的渐近复杂度为n ^ 2。

3的复杂度为O(I * J)，其中I和J是c1和c2输入的大小。

- David Gladfelter

Answer 4

说实话，O(n²+n)和O(n²+2n)是相同的。

- brian

Answer 5

3的复杂度为O(m*n)。 不存在O(n²+n)或O(n²+2n)的复杂度。实际上它只是O(n²)。这是因为n是o(n²)。

O(log(n))的例子是二分查找。

O(n*log(n))的例子是归并排序。

- shura

---

由于定义上来说Big-O是最坏情况，如果你有一个O(n^2)的算法，那么O(n^2+n)在长期来看并没有什么不同，因为n^2的量级要大于n。 - Brian T Hannan