Грокаем алгоритмы

Аналогичные рассуждения применимы к быстрой сортировке. Работоспособность алгоритма для базового случая — массивов с размером 0 и 1 — была продемонстрирована. В индукционном переходе я показал, что если быстрая сортировка работает для массива из 1 элемента, то она будет работать для массива из 2 элементов. А если она работает для массивов из 2 элементов, то она будет работать для массивов из 3 элементов и т.д. Из этого можно сделать вывод, что быстрая сортировка будет работать для всех массивов любого размера. Я не буду подробно рассматривать доказательства по индукции, но это интересный метод, который идет рука об руку со стратегией «разделяй и властвуй».

А вот как выглядит программный код быстрой сортировки:

def quicksort(array):

  if len(array) < 2:

    return array         Базовый случай: массивы с 0 и 1 элементом уже "отсортированы"

  else:

    pivot = array[0]  Рекурсивный случай

    less = [i for i in array[1:] if i < pivot]  Подмассив всех элементов, меньших опорного

    greater = [i for i in array[1:] if i > pivot] Подмассив всех элементов, больших опорного

    return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])

Снова об «O-большом»

Алгоритм быстрой сортировки уникален тем, что его скорость зависит от выбора опорного элемента. Прежде чем рассматривать быструю сортировку, вспомним наиболее типичные варианты времени выполнения для «O-большое».

Оценки для медленного компьютера, выполняющего 10 операций в секунду

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

Для каждого времени выполнения также приведен пример алгоритма. Возьмем алгоритм сортировки выбором, о котором вы узнали в главе 2. Он обладает временем O(n2), и это довольно медленный алгоритм.

Другой алгоритм сортировки — так называемая сортировка слиянием — работает за время O(n log n). Намного быстрее! С быстрой сортировкой дело обстоит сложнее. В худшем случае быстрая сортировка работает за время O(n2).

Ничуть не лучше сортировки выбором! Но это худший случай, а в среднем быстрая сортировка выполняется за время O(n log n). Вероятно, вы спросите:

• что в данном случае понимается под «худшим» и «средним» случаем?

• если быстрая сортировка в среднем выполняется за время O(n log n), а сортировка слиянием выполняется за время O(n log n) всегда, то почему бы не использовать сортировку слиянием? Разве она не быстрее?

Сортировка слиянием и быстрая сортировка

Допустим, у вас имеется простая функция для вывода каждого элемента в списке:

def print_items(list):

  for item in list:

    print item

Эта функция последовательно перебирает все элементы списка и выводит их. Так как функция перебирает весь список, она выполняется за время O(n). Теперь предположим, что вы изменили эту функцию и она делает секундную паузу перед выводом:

from time import sleep

def print_items2(list):

  for item in list:

    sleep(1)

    print item

Перед выводом элемента функция делает паузу продолжительностью в 1 секунду. Предположим, вы выводите список из пяти элементов с использованием обеих функций:

Обе функции проходят по списку один раз, и обе выполняются за время O(n). Как вы думаете, какая из них работает быстрее? Я думаю, print_items работает намного быстрее, потому что она не делает паузу перед выводом каждого элемента. Следовательно, даже при том, что обе функции имеют одинаковую скорость «O-большое», реально print_items работает быстрее. Когда вы используете «O-большое» (например, O(n)), в действительности это означает следующее:

Здесь c — некоторый фиксированный промежуток времени для вашего алгоритма. Он называется константой. Например, время выполнения может составлять 10 миллисекунд * n для print_items против 1 секунды * n для print_items2.

Обычно константа игнорируется, потому что если два алгоритма имеют разное время «O-большое», она роли не играет. Для примера возьмем бинарный и простой поиск. Допустим, такие константы присутствуют в обоих алгоритмах.

Первая реакция: «Ого! У простого поиска константа равна 10 миллисекундам, а у бинарного поиска – 1 секунда. Простой поиск намного быстрее!» Теперь предположим, что поиск ведется по списку из 4 миллиардов элементов. Время будет таким:

Как видите, бинарный поиск все равно работает намного быстрее. Константа ни на что не повлияла.