确定性的时间复杂度 select

Question

假设我做k组。由于输入数组的大小不是常量，因此一组中的元素数将为 n/k。对此进行排序需要 (n/k)log(n/k)。对于 k 组，它将是 (n)log(n/k) 这是 O(nlogn)。那算法怎么是O(n)？

编辑：来自 Gfg https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/amp/

kthSmallest(arr[0..n-1], k)
1) Divide arr[] into ⌈n/5⌉ groups where size of each group 
is 5 except possibly the last group which may have less     
than 5 elements.
2) Sort the above created ⌈n/5⌉ groups and find median 
of all groups. Create an auxiliary array ‘median[]’ and 
store medians of all ⌈n/5⌉ groups in this median array.
// Recursively call this method to find median of 
median[0..⌈n/5⌉-1]
3) medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)
4) Partition arr[] around medOfMed and obtain its 
position.
pos = partition(arr, n, medOfMed)
5) If pos == k return medOfMed
6) If pos > k return kthSmallest(arr[l..pos-1], k)
7) If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)

Answer 1

您不是在对每个组中的元素进行排序，您只是在寻找它们的中位数，即 O(n/k)（理论上这是在 n/k 的较小且恒定的值上完成的，然后只是被认为是 O(1))。所以你必须运行 O(n/k) 算法 k 次，这会产生 O(n).

请注意，即使您进行排序，由于该算法使用常数组大小，因此每个组的大小：n/k = C（对于某些常数C)，你会得到：O(nlog(n/k)) = O(nlog(C)) = O(n)

确定性的时间复杂度 select

Time complexity of deterministic select

sorting

algorithm

time-complexity