SubTree
Вход
Все статьи и конспекты
СортировкиMergeSortQuickSortДерево решенийАлгоритмы
3 мин чтение

Алгоритмы сортировки и теоретическая граница Ω(Nlog⁡N)\Omega(N \log N)

Исчерпывающий разбор алгоритмов сортировки: Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort. Математический вывод нижней границы сложности сортировок сравнением через дерево решений высоты h >= log2(N!).

Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.

Введение в задачу сортировки

Задача сортировки: Для входной последовательности ⟨a1,a2,…,an⟩\langle a_1, a_2, \dots, a_n \rangle найти перестановку ⟨a1′,a2′,…,an′⟩\langle a'_1, a'_2, \dots, a'_n \rangle, такую что a1′≤a2′≤⋯≤an′a'_1 \le a'_2 \le \dots \le a'_n.

Теоретическая нижняя граница сложности: Дерево решений

Любая сортировка, использующая только попарные сравнения элементов (ai≤aja_i \le a_j), может быть представлена в виде бинарного дерева решений (Decision Tree):

  • Каждый внутренний узел — это проверка ai≤aja_i \le a_j;

  • Левая ветвь соответствует условию ≤\le, правая — >>;

  • Каждый лист соответствует одной из N!N! возможных перестановок массива.

    • Математический вывод:

  • Дерево с LL листьями и высотой hh удовлетворяет неравенству:
    • L≤2hL \le 2^h
  • Чтобы алгоритм мог отсортировать любую перестановку, число листьев должно быть не меньше числа всех перестановок:
    • N!≤L≤2h  ⟹  2h≥N!N! \le L \le 2^h \implies 2^h \ge N!
  • Логарифмируя обе части:
    • h≥log⁡2(N!)h \ge \log_2(N!)
  • Применяя формулу Стирлинга ln⁡(N!)=Nln⁡N−N+O(ln⁡N)\ln(N!) = N \ln N - N + O(\ln N):
    • h≥∑i=1Nlog⁡2i≥∑i=N/2Nlog⁡2N2=N2log⁡2N2=Ω(Nlog⁡N)h \ge \sum_{i=1}^N \log_2 i \ge \sum_{i=N/2}^N \log_2 \frac{N}{2} = \frac{N}{2} \log_2 \frac{N}{2} = \Omega(N \log N)
    Теорема: Любой алгоритм сортировки, основанный на сравнениях, в худшем случае требует Ω(Nlog⁡N)\Omega(N \log N) операций.

    Сравнительная таблица алгоритмов сортировки

    АлгоритмЛучшее времяСреднее времяХудшее времяПамятьСтабильностьМетод
    **Bubble Sort**17 (с флагом)181920ДаОбмен
    **Insertion Sort**21222324ДаВставки
    **Merge Sort**25262728ДаРазделяй и властвуй
    **Quick Sort**29303132НетРазделяй и властвуй
    **Heap Sort**33343536НетПирамида
    cpp 
    // Реализация MergeSort
void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> left(arr.begin() + l, arr.begin() + m + 1);
    vector<int> right(arr.begin() + m + 1, arr.begin() + r + 1);
    int i = 0, j = 0, k = l;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) arr[k++] = left[i++];
        else arr[k++] = right[j++];
    }
    while (i < left.size()) arr[k++] = left[i++];
    while (j < right.size()) arr[k++] = right[j++];
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

    Что дальше?

    Закрепите материал задачей: Повторить число.

    Изучено — к практике →

    Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».

    Далее: Метод декомпозиции, Master Theorem и Задача о паре ближайших точек