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

Question

是O(n^2 log n)吗？你能说明它是如何推导出来的吗？ O(n^2 log n) 与 O((n^2) * (log n)) 相同吗？

Answer 1

做某事 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))

Answer 2

严格推导:

根据定义

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)).

What is the running time of an O(n log n) sort done n times?