Быстрый выбор средней сложности по времени O (n) [КАК?] - PullRequest
Новая
       21

Быстрый выбор средней сложности по времени O (n) [КАК?]

0 голосов
/ 11 февраля 2019

Я изучал QuickSelect, чтобы найти Kth наименьшее число.Я понял программу.Но я застрял в том, что средняя сложность 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)?Кто-нибудь может объяснить мне это подробно?

1 Ответ

0 голосов
/ 11 февраля 2019

Я думаю, что ваш вопрос не является специфическим для QuickSelect.Вы спрашиваете, в чем разница между нотацией большого О и средней нотацией тета (Θ).

Нотация большого О описывает наибольшую потенциальную сложность, которую будет использовать алгоритм.

С другой стороны, нотация the - это средняя сложность всех возможных комбинаций входных данных для задачи.

Существует также нотация омега (Ω) для наилучшей сложности случая.

Алгоритм быстрого выбора следует за подобной сложностью быстродействующей сортировке, и вы правы, большая буква O для обоих - O (n ^ 2), но в среднем случае они лучше.

Есливам нужно более конкретное объяснение, почему средний случай является линейным, прочитайте ответ в этом посте .

...