QuickSelect 平均时间复杂度 O(n) [如何？]

Question

我正在学习 QuickSelect 以找到第 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)如何？谁能给我详细解释一下？

Answer 1

我认为您的问题不是针对 QuickSelect 的。你问的是大 O 表示法和平均 Theta (Θ) 表示法有什么区别。

大 O 表示法描述了算法将使用的最大潜在复杂性。

另一方面，Θ 符号是问题输入的所有可能组合的平均复杂度。

还有用于最佳情况复杂度的欧米茄 (Ω) 表示法。

快速 select 算法遵循与快速排序相似的复杂性，你是对的，两者的大 O 表示法都是 O(n^2)，但在一般情况下它们更好。

如果您需要更具体的解释为什么平均情况是线性的，请阅读此 post 中的答案。

QuickSelect 平均时间复杂度 O(n) [如何？]

QuickSelect average time complexity O(n) [HOW?]

java

time-complexity

quickselect