Сложность времени упрощенной сортировки с 3 путями - PullRequest
Новая
       82

Сложность времени упрощенной сортировки с 3 путями

0 голосов
/ 26 апреля 2018

Ниже приведен мой алгоритм, упрощенный подход к алгоритму трехстороннего разбиения Дейкстры для общего списка: 

static <T extends Comparable> void dutchSort(List<T> list, int left, int right) {
    if (left >= right) return;

    T pivot = list.get(left);

    // smaller - index of the last element smaller than pivot value
    // equal - index of the last element equal to pivot value
    // larger - index of the first element larger than pivot value
    int smaller = left-1, equal = left, larger = right;

    // before sorting is completed, 'equal' is the current value
    // much like 'i' in a for-loop
    // O(N) time
    while (equal < larger) {
        if (list.get(equal).compareTo(pivot) < 0)
            Collections.swap(list, equal, ++smaller);
        else if (list.get(equal).equals(pivot))
            equal++;
        else
            Collections.swap(list, equal, --larger);
    }

    // recursively sort smaller subarray
    dutchSort(list, left, smaller+1);

    // recursively sort larger subarray
    dutchSort(list, equal, list.size());
}

Это пространство O (1), и я думаю, что это O (N ^ N)время, но я не уверен. В сообщении Toptal о трехсторонней быстрой сортировке говорится, что это O (N ^ 2), но разница в том, что мой алгоритм гораздо более наивен.Мой мыслительный процесс таков: цикл while занимает O (N) времени, и в худшем случае (все N элементов различны?) Проблема разбита на N подмассивов размера 1.

Я попробовалОсновная теорема, но я не был уверен ни в одном из значений переменных.Я думаю, что количество подзадач равно 2, каждый рекурсивный вызов уменьшает проблему в 2 раза, и объединение подзадач требует O (1) работы.

Все это только догадки, и я, вероятно, довольновыкл, так что я действительно хотел бы строго решить сложность времени.

Правильно ли время O (N ^ N)?И если да, то почему?

Большое спасибо:)

1 Ответ

0 голосов
/ 28 апреля 2018

Таким образом, цикл while равен O (n) при первоначальном вызове.Если мы примем массив [1, 2, 3, 4, 5], то первый раз в цикле list[equal] == pivot, и мы увеличиваем equal.

Второй и последующие моменты в цикле, list[equal] > pivot, поэтому мы уменьшаемlarger и поменяйте местами с этим элементом.Когда цикл закончен, у вас есть equal=1, а smaller не изменился.Ваши рекурсивные вызовы становятся: 

dutchSort(list, 0, 0)
dutchSort(list, 1, n)

Итак, один из предметов выпал.

Сделайте то же умственное упражнение a для еще нескольких глубин рекурсии, и я думаю, вы получитеИдея о том, как работает разбиение.

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

Когда все элементы равны, алгоритм равен O (N).

Я думаю, что сложность алгоритма определяется количеством уникальных предметов.Не похоже, что начальный порядок массива будет иметь какое-либо влияние.

...