通过插入函数“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) ??
最佳答案
Log(n!) 受日志规则 log(n^n) 的限制,其 n*logn
1*2*3*4*....*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)
关于c++ - 为什么创建堆数组的时间复杂度不是O(log(n!))而是O(nlogn)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57843488/