我正在学习快速选择以找到第 K 个最小的数字。我理解了这个程序。但我对 QuickSelect 的平均时间复杂度是 O(n) 感到困惑。
我已经尝试了 Java 中的代码并且它有效。但我被时间复杂性困住了。
public class KthSmallestNumberUsingQuickSelect {
int findKthNumber(int arr[], int left, int right, int k ) {
if(k > 0 && k <= right - left + 1) {
int pos = partition(arr,left,right);
if(pos - left == k - 1)
return arr[pos];
if(pos - left > k - 1)
return findKthNumber(arr, left, pos - 1, k);
System.out.println(k - pos + left - 1);
return findKthNumber(arr, pos + 1, right, k - pos + left - 1);
}
return Integer.MAX_VALUE;
}
int partition(int arr[], int left, int right) {
int i = left ;
int j;
int x = arr[right];
int temp = 0;
for(j=left; j<right; j++ ) {
if(arr[j] <= x) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
temp = arr[i];
arr[i] = x;
arr[right] = temp;
return i;
}
public static void main(String[] args) {
KthSmallestNumberUsingQuickSelect kq = new KthSmallestNumberUsingQuickSelect();
int arr[] = {7,10,4,3,20,15};
int k = 3;
System.out.println(kq.findKthNumber(arr,0,arr.length-1, k));
}
}
平均时间复杂度 O(n) 是多少?任何人都可以向我详细解释一下吗?