你这个问题是自己想出来的吧？
第一，你指的时间复杂度是大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，则从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)
第一，你指的时间复杂度是大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，则从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)
温馨提示：内容为网友见解，仅供参考
无其他回答
相似回答
