鍍金池/ 問答/人工智能  Python  網(wǎng)絡(luò)安全/ 長度為n的列表，查找出前k大的元素，這種算法的時(shí)間度是少的嗎

長度為n的列表，查找出前k大的元素，這種算法的時(shí)間度是少的嗎

如果求前10大的元素，還有更少時(shí)間的算法嗎
純屬好奇，望大俠不吝賜教

###列表
temp0 =  range(2000,5001)
temp1 =  range(200,500)
temp2 =  range(801,8000)
a = sorted(temp0)
b = sorted(temp1)
c = sorted(temp2)
d = b + c + a

### 計(jì)算過程
temp = []
t = 0
for i in d:
    t += 1
    le = len(temp)
    if le < 10:
        temp.insert(0,i)
        temp = sorted(temp)        
    else:
        f = temp[0]
        if i > f:
            temp[0] = i
            temp = sorted(temp) 
print("總數(shù)：",len(d))
print("查詢次數(shù)：",t)
print(temp)
#計(jì)算結(jié)果
總數(shù)： 10500
查詢次數(shù)： 10500
[7990, 7991, 7992, 7993, 7994, 7995, 7996, 7997, 7998, 7999]
回答
編輯回答
傲嬌范

你這已經(jīng)是線性時(shí)間復(fù)雜度了，再低的話除非是對數(shù)時(shí)間

2017年11月9日 16:38
編輯回答
背叛者

可以試試堆排序

2018年1月6日 04:51
編輯回答
拼未來
import heapq
d = list(range(200,500)) +  list(range(801,8000)) + list(range(2000,5001))
heapq.heapify(d)    # 堆樹，時(shí)間復(fù)雜度O(n)
heapq.nlargest(10, d)

你的算法的插入后排序，可以用二分法插入優(yōu)化

import bisect

# temp.insert(0,i)
# temp = sorted(temp) 優(yōu)化為
bisect.insort(temp, i)

# temp[0] = i
# temp = sorted(temp) 優(yōu)化為
temp.pop(0)
bisect.insort(temp, i)
2017年2月24日 08:00