了解大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)
  {
  }
}

Answer 1

如果两个集合具有相同的大小,则3是O(n*m)或O(n ^ 2).

O(n ^ 2 + n)是没有意义的,因为n小于n ^ 2.只需写入O(n ^ 2).

最体面的比较排序算法运行在O(n*log(n)).如果您不知道,请查看维基百科.

一个二进制搜索是O(日志(N)).

Answer 2

外部foreach执行n = | c1| times(其中| 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(nlogn)

使用上面的算法,但现在你必须找到字典中的每个单词.