O(n log n)次排序的运行时间是多少?

Question

是O(n^2 log n)吗?你能说明它是如何推导出来的吗?O(n^2 log n)等于O((n^2) * (log n))吗?

Answer 1

严格推导:

由定义

T(n) = O(n Log(n)) <=> for some N and C,  n > N => T(n) < C.n.log(n).

那么明显

for these N and C, n > N => n.T(n) < C.n².log(n)

这意味着

n.T(n) = O(n²log(n)).

Answer 2

做n的事情需要O(n)的时间。n log n是n * log n的另一种写法所以我们得到:

  O(n) * O(n * log n)
= O((n) * (n * log n)) 
= O(n * n * log n)
= O(n^2 * log n)

是的，你所展示的两种写法是一样的。然而，这是完全不同的:O(n^(2 log n))