排序算法的时间复杂度计算

问题:有N个数排序,每次排序完把排在最后的数【删掉】,重新继续排序【直至】剩下L个数停止操作。
~~我知道一次排序的算法复杂度为N*logN~~但是这种动态的就不知道了~请高手们指点一下~!万分感谢!

你这个问题是自己想出来的吧?
第一,你指的时间复杂度是大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表示法数学描述起来要扯到极限什么的,不直观,只要知道是他表示的是一个上界但不是上确界就好了

温馨提示:答案为网友推荐,仅供参考