algorithm - 如何找到 KthLargest 算法的平均情况？

Question

我知道最好的情况是 B(1)。最坏的情况是 W(n+1)，因为在搜索列表时，因为您必须比较最后一个元素的两侧。我最困惑的是这个算法的平均情况。

findKthLargest (list, N, K)
for i = 1 to K do
    largest = list[1]
    largestLocation = 1
    for j = 2 to N-(i-1) do
        if list[j] > largest then
            largest = list[j]
            largestLocation = j
        endIf
    endFor
    swap(list[N - (i-1)], list[largestLocation] )
endFor
return largest

标签： algorithmaverageanalysis