排序算法的时间复杂度计算
发布网友
发布时间：2022-04-21 19:29
共1个回答
热心网友
时间：2022-05-22 02:52
第一，你指的时间复杂度是大O表示法的复杂度，也就是一个上界，但不是上确界，所以就算你以一种方式中断排序过程，时间复杂度还是O(N*logN)，假设排序过程还能执行的话。
第二，达到O(N*logN)的排序算法，以快速排序为例，快速排序不知道你看过没有，它不像选择排序或者冒泡排序那样，每一趟可以确定一直最大或者最小值，对于快速排序，每一趟排序后如果你删掉最后一个元素将导致整个算法失效。如果你要用这种删除元素方法的话，只能采用冒泡排序或者选择排序，时间复杂度是O(N^2)
所以，我猜想你是不是想做类似于在N个元素中寻找前K个最大者之类的事情（K=N-L）
如果是这样的话，有复杂度是O(N*logK)的算法，利用快速排序中的partition操作
经过partition后，pivot左边的序列sa都大于pivot右边的序列sb；
如果|sa|==K或者|sa|==K-1，则数组的前K个元素就是最大的前K个元素，算法终止;
如果|sa|<K-1，则从sb中寻找前K-|sa|-1大的元素;
如果|sa|>K，则从sa中寻找前K大的元素。
一次partition(arr,begin,end)操作的复杂度为end-begin，也就是O(N)，最坏情况下一次partition操作只找到第1大的那个元素，则需要进行K次partition操作，总的复杂度为O(N*K)。平均情况下每次partition都把序列均分两半，需要logK次partition操作，总的复杂度为O(N*logK)。
由于K的上界是N，所以以N表示的总复杂度还是O(N*logN)追问嗯嗯~谢谢你~~明白一些了~这个问题确实是我自己的一个问题~~其实是N个数先排序，然后把最小的数删掉~【再把剩下的数中任意替换掉2个】~然后重新排序删掉最小的~这样循环直到L个~就像你说的我用的其实是冒泡排序，你说的Partition操作我也不是很了解，如果现在用冒泡排序法解决这个问题，那时间复杂度要怎么算呢？是不是 第一次N^2，第二次（N-1）^2 呢？这样循环N-L次的话总的复杂度可以算作O(N^3)吗？ 非常感谢！一定为您加分！
追答注意到你用冒泡法的时候，只要求找到最小的一个元素就好了，相当于只需要做冒泡法的第一轮冒泡即可，所以每次找最小再删除的时候时间复杂度是O(N)不是O(N^2)，循环N-L次的时间复杂度是O(N^2)
时间复杂度不是计算次数，O((N-1)^2)实际上就是O(N^2)，大O表示法数学描述起来要扯到极限什么的，不直观，只要知道是他表示的是一个上界但不是上确界就好了
