Статейка номер 9. Начала алгоритмов

Часть первая. Немного теории

Шо такое алгоритм? Алгоритм это система из операций, составленных по определённым правилам, и призванных решать поставленную задачу. Для тупеньких: собраться в шкалку уже есть алгоритм, т.к. имеется задача и имеется система из действий.

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

Анализ алгоритмов в основном сводится к анализу по двум параметрам — время выполнения и затраты памяти. Причём тут, сука, полный эскобаритет: выигрывая по времени, мы гарантированно будем проёбывать по памяти, и наоборот.

Отдельных слов заслуживает характеристика по времени, выражаемая функцией O.

№  |  Функция      |  Пояснение

---+---------------+------------------------------------------------

1  |  O(1)         |  Все действия выполняются единожды, независимо от n

2  |  O(log(n))    |  Логирифмическая зависимость от n

3  |  O(n)         |  Линейная зависимость от n

4  |  O(n * log(n))|  Линерефмическая зависимость от n

4  |  O(n**2)      |  Квадратичная зависимость от n

5  |  O(n**3)      |  Кубическая зависимость от n

6  |  O(2**n)      |  Экспоненциальная зависимость от n

6  |  O(n!)        |  Факториальная зависимость от n

В таблице функции расположены от более быстрых, до медленных.

Например, O(1) означает, что алгоритм выполняется с одинаковым временем, какие бы входные данные не были переданы. O(n) означает, что чем больше данных, тем медленнее программа. O(n**2), например, перебор от 0000 до 9999. O(n**3) — действия с матрциами, и т.д.

В матан углубляться не будем, потому что «не лезь, оно тебя сожрёт!». Пределы сосатб.

Часть вторая. Сортировки

А вот теперь мы уже переходим конкретно к старой доброй змее.

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

Как видим из этого графика, наиболее рациональный алгоритм будем характеризоваться функцией log(n), а самый пососный — n! (пососен настолько, что на графике впадлу указывать). Но, как можно заметить, до определённого момента n выглядит приятнее, чем nlog(n), а 2**n с количеством элементов работает хуже, чем n**2 и даже n**3. Потому всё, сцуко, охуеть как неоднозначно.

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

Теперь пройдёмся по основным и самым распространённым алгоритмам. И вот тут будет намного интереснее. Работаем так: первую сортировку я объясняю подробно, на пальцах, даже код дам. А вот остальные нужно будет написать самостоятельно, имея на руках описание принципа и гифак с примером работы.

Сортировка пузырьком.

Почему пузырьком? Хуй его знает.

Работает эта тема так:

8 2 5 4 3 6 1 3      - входной массив

Первый проход

2 8 5 4 3 6 1 3      - 2 < 8, заменены местами

2 5 8 4 3 6 1 3      - 5 < 8, заменены местами

2 5 4 8 3 6 1 3      - 4 < 8, заменены местами

2 5 4 3 8 6 1 3      - 3 < 8, заменены местами

2 5 4 3 6 8 1 3      - 6 < 8, заменены местами

2 5 4 3 6 1 8 3      - 1 < 8, заменены местами

2 5 4 3 6 1 3 8      - 3 < 8, заменены местами

Первый проход

2 5 4 3 6 1 3 8      - 2 < 5, оставлены на местах

2 4 5 3 6 1 3 8      - 4 < 5, заменены местами

2 4 3 5 6 1 3 8      - 3 < 5, заменены местами

2 4 3 5 6 1 3 8      - 5 < 6, оставлены на местах

2 4 3 5 1 6 3 8      - 1 < 6, заменены местами

2 4 3 5 1 3 6 8      - 3 < 6, заменены местами

2 4 3 5 1 3 6 8      - 6 < 8, оставлены на местах

Третий проход

2 4 3 5 1 3 6 8      - 2 < 4, оставлены на местах

2 3 4 5 1 3 6 8      - 3 < 4, заменены местами

2 3 4 5 1 3 6 8      - 4 < 5, оставлены на местах

2 3 4 1 5 3 6 8      - 1 < 5, заменены местами

2 3 4 1 3 5 6 8      - 3 < 5, заменены местами

2 3 4 1 3 5 6 8      - 5 < 6, оставлены на местах

2 3 4 1 3 5 6 8      - 6 < 8, оставлены на местах

Четвёртый проход

2 3 4 1 3 5 6 8      - 2 < 3, оставлены на местах

2 3 4 1 3 5 6 8      - 3 < 4, оставлены на местах

2 3 1 4 3 5 6 8      - 1 < 4, оставлены на местах

2 3 1 3 4 5 6 8      - 3 < 4, заменены местами

2 3 1 3 4 5 6 8      - 4 < 5, оставлены на местах

2 3 1 3 4 5 6 8      - 5 < 6, оставлены на местах

2 3 1 3 4 5 6 8      - 6 < 8, оставлены на местах

Пятый проход

2 3 4 1 3 5 6 8      - 2 < 3, оставлены на местах

2 3 4 1 3 5 6 8      - 3 < 4, оставлены на местах

2 3 1 4 3 5 6 8      - 1 < 4, заменены местами

2 3 1 3 4 5 6 8      - 3 < 4, заменены местами

2 3 1 3 4 5 6 8      - 4 < 5, оставлены на местах

2 3 1 3 4 5 6 8      - 5 < 6, оставлены на местах

2 3 1 3 4 5 6 8      - 6 < 8, оставлены на местах

Шестой проход

2 3 1 3 4 5 6 8      - 2 < 3, оставлены на местах

2 1 3 3 4 5 6 8      - 1 < 3, заменены местами

2 1 3 3 4 5 6 8      - 3 == 3, оставлены на местах

2 1 3 3 4 5 6 8      - 3 < 4, оставлены на местах

2 1 3 3 4 5 6 8      - 4 < 5, оставлены на местах

2 1 3 3 4 5 6 8      - 5 < 6, оставлены на местах

2 1 3 3 4 5 6 8      - 6 < 8, оставлены на местах

Седьмой проход

1 2 3 3 4 5 6 8      - 1 < 2, заменены местами

1 2 3 3 4 5 6 8      - 2 < 3, оставлены на местах

1 2 3 3 4 5 6 8      - 3 == 3, оставлены на местах

1 2 3 3 4 5 6 8      - 3 < 4, оставлены на местах

1 2 3 3 4 5 6 8      - 4 < 5, оставлены на местах

1 2 3 3 4 5 6 8      - 5 < 6, оставлены на местах

1 2 3 3 4 5 6 8      - 6 < 8, оставлены на местах

Восьмой проход

1 2 3 3 4 5 6 8      - 1 < 2, оставлены на местах

1 2 3 3 4 5 6 8      - 2 < 3, оставлены на местах

1 2 3 3 4 5 6 8      - 3 == 3, оставлены на местах

1 2 3 3 4 5 6 8      - 3 < 4, оставлены на местах

1 2 3 3 4 5 6 8      - 4 < 5, оставлены на местах

1 2 3 3 4 5 6 8      - 5 < 6, оставлены на местах

1 2 3 3 4 5 6 8      - 6 < 8, оставлены на местах

Прога проверяет, меньше ли число слева числа справа. Если оно реально меньше — оставляет на местах. Если нет — переставляет. Массив считается отсортированным, если при полном проходе все элементы остались на своих местах. (Что, кстати говоря, можно отсечь нахуй при желании)

li = [8, 2, 5, 4, 3, 6, 1, 3]

n = 1  while n < len(li):      for i in range(len(li)-n):           if li[i] > li[i+1]:                li[i],li[i+1] = li[i+1],li[i]      n += 1

Ну и сам код сортировки. Который, кстати, не такой монструозный, как визализация его действия. Сложность алгоритма: O(n?)

Сортировка вставками

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

Гномья сортировка

Алгоритм, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Сложность алгоритма: O(n?)

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

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементамкоторых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Основной её подвох в том, что лучшее время точно такое же, как худшее и среднее. Если все сортировки выше хуярят либо n в лучшем случае, n? в худшем, то эта стабильно еборит n*log(n), что, казалось бы, довольно неплохо. Но отсутствие ускорения в «более отсортированных» массивах выглядит удручающе.

Быстрая сортировка (сортировка Хоара)

Даю тупо по фану, ибо реализовать это тупо анрил на текущем уровне людей, изучающих питон по статейкам.

Общая идея алгоритма состоит в следующем:

• Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность (см.ниже).
• Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».
• Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.

Средняя сложность n * log(n), в лучшем случае разгоняется до log(n), в худшем скатывается до n?. Загадка о трёх стульях, но на всех хуи, гыг.

Источник: m.vk.com

Комментарии: