将数组的元素插入映射的时间复杂度是多少？ [重复]

Question

此问题已经在这里有了答案：

Is log(n!) = Θ(n·log(n))?（9个答案）

[<5小时前关闭。

如果插入元素在地图中花费log（N）时间，其中N是地图的大小。然后一一插入数组的元素log（1）+ log（2）+ .... + log（N）= log（N！）复杂度。但是使元素排序的通常最好的复杂度是Nlog（N），我在哪里出错？

Answer 1

无处，O(log n!) == O(n log n)。证明有点数学。

首先，我们有log(n!) = log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n) = n log(n)。另一方面，我们还得到以下内容

2 log(n!) = 2*(log(1) + log(2) + ... + log(n)) 
          = (log(1) + log(n)) + (log(2) + log(n-1)) + ... + (log(i) + log(n-i+1)) + ... + (log(n) + log(1)) 
          = log(1*n) + log(2*(n-1)) + ... + log(i*(n-i+1)) + ... log(n*1) 
          >= log(n) + ... + log(n) = n log(n)

i*(n-i+1) = i*n - i*i + i >= n以来我们得到的不等式（似乎有些神秘，但它基本上说乘积比求和的增长快）。 
所以我们有log(n!) <= n log(n) <= 2 log(n!)。通过O标记的定义，这意味着O(log(n!)) = O(n log(n))。