为什么创建堆数组的时间复杂度不是O(log(n!))而是O(nlogn)？

Question

通过插入函数 "insert(A,n)" 在堆中插入新元素需要 O(log n) 时间（其中 n 是数组 'A' 中元素的数量）。插入函数如下：

void insert(int A[], int n)
{
   int temp,i=n;
   cout<<"Enter the element you want to insert";
   cin>>A[n];
   temp=A[n];
   while(i>0 && temp>A[(i-1)/2])
   {
      A[i]=A[(i-1)/2];
      i=(i-1)/2;
   }
   A[i]=temp;
}

插入函数的时间复杂度为 O(log n)。

将数组转换为堆数组的函数如下：

void create_heap()
{
   int A[50]={10,20,30,25,5,6,7};
   //I have not taken input in array A from user for simplicity.
   int i;
   for(i=1;i<7;i++)
   {
      insert(A,i);
   }
}

假设这个函数的时间复杂度是O(nlogn)。

-> 但插入函数在每次调用中最多有 'i' 个要比较的元素。即，对于每个调用，单个运行循环的时间复杂度为 O(log i)。

-> 所以首先是 log1，然后是 log2，然后是 log3，依此类推直到 log6。

-> 所以对于一个数组的 n 个元素，总的时间复杂度是 log2 + log3 + log4 +....logn

-> 这将是 log(2x3x4x...xn) = log(n!)

那么为什么时间复杂度不是O(log(n!))而是O(nlogn)??

Answer 1

Log(n!) 由日志规则中的 log(n^n) 限制其 n*logn

1*2*3*4*....*n = n!
n*n*n*n*....*n = n^n

清楚n！ < n^n

那么为什么在 O(logn!) 是更紧的界限时使用 O(nlogn)？因为 nlogn 以 log(n!) 为界，令人惊讶，不是吗？

log(1*2*3*4*....*n) = log(1) + log(2) + ... + log(n)

让我们扔掉上半场

log(1*2*3*4*....*n) > log(n/2) + log((n/2) + 1) + log((n/2)+2) + ... + log(n) 
                    > log(n/2) + log(n/2) + ... + log(n/2) 
                    = n/2*log(n/2) = O(nlogn)

为什么创建堆数组的时间复杂度不是O(log(n!))而是O(nlogn)？

Why is the time complexity of creating a heap array not O(log(n!)) instead of O(nlogn)?

c++

time-complexity

heap

heapsort