1. Введение в теорию алгоритмов, О-нотация и встроенные методы сортировки в Python
Введение в теорию алгоритмов, О-нотация и встроенные методы сортировки в Python
Добро пожаловать на курс «Алгоритмы сортировки на Python: от теории к практике». Мы начинаем наше путешествие в мир эффективного кода с фундаментальных понятий. Сортировка данных — это не просто упорядочивание чисел или строк. Это «Hello World» в мире алгоритмической оптимизации. Понимая, как работают сортировки, вы научитесь оценивать эффективность кода, работать со сложными структурами данных и проходить технические собеседования в ведущие IT-компании.
В этой вводной статье мы разберем, что такое алгоритм, как измеряется его скорость (и почему секундомер здесь не поможет), а также посмотрим, как сортировка реализована в самом языке Python «из коробки».
Что такое алгоритм?
В самом широком смысле алгоритм — это точная последовательность действий, преобразующая входные данные в результат за конечное число шагов. Это рецепт. Если вы готовите пирог, у вас есть входные данные (мука, яйца, сахар) и инструкция. Если инструкция верна, вы гарантированно получите пирог.
В программировании алгоритм должен обладать следующими свойствами:
Оценка сложности алгоритмов: Big O Notation
Представьте, что вы написали функцию сортировки. Как понять, хорошая она или плохая? Можно запустить её на компьютере и замерить время. Но это ненадежный метод: на мощном сервере код будет работать быстрее, чем на старом ноутбуке. Нам нужна метрика, не зависящая от «железа».
Здесь на сцену выходит асимптотическая сложность или О-нотация (Big O Notation). Она описывает, как растет время выполнения алгоритма (или потребляемая память) при увеличении объема входных данных.
!График сравнения скоростей роста функций сложности алгоритмов
Основные классы сложности
Мы записываем сложность как , где — это размер входных данных, а — функция, описывающая зависимость количества операций от .
Рассмотрим самые популярные классы сложности от самого быстрого к самому медленному:
* — Константное время. Время выполнения не зависит от количества данных. Пример: получение элемента списка по индексу.
* — Логарифмическое время. Время растет очень медленно. Характерно для бинарного поиска. Если увеличится в 1000 раз, время увеличится лишь на константу.
* — Линейное время. Время растет прямо пропорционально данным. Если данных стало в 2 раза больше, алгоритм работает в 2 раза дольше. Пример: обычный проход циклом for по списку.
* — Линеаримическое время. Стандарт для эффективных алгоритмов сортировки (например, QuickSort или MergeSort). Это чуть медленнее, чем линейное время, но значительно быстрее квадратичного.
* — Квадратичное время. Время растет пропорционально квадрату количества данных. Характерно для простых алгоритмов сортировки с вложенными циклами (например, Пузырьковая сортировка). При увеличении данных в 10 раз, время вырастет в 100 раз.
Математически это можно выразить так:
Где — время выполнения алгоритма, — некоторая константа, зависящая от скорости процессора, а — размер входных данных. В О-нотации мы отбрасываем константу и младшие слагаемые, оставляя только доминирующий член , так как именно он определяет скорость роста при больших .
Временная и пространственная сложность
Важно помнить, что мы оцениваем два ресурса:
Идеальный алгоритм работает за времени и памяти, но в реальности нам часто приходится жертвовать памятью ради скорости и наоборот.
Задача сортировки
Формализуем задачу, которую мы будем решать на протяжении всего курса.
Дана последовательность чисел (или других сравнимых объектов) .
Где — исходный массив, — элемент массива под индексом , а — общее количество элементов.
Необходимо найти такую перестановку , чтобы выполнялось условие:
Где — первый элемент отсортированного массива, — второй элемент, и так далее до последнего элемента , при этом каждый следующий элемент больше или равен предыдущему.
Встроенные методы сортировки в Python
Прежде чем писать свои реализации (что мы будем делать в следующих уроках для учебных целей), важно знать, как сортировать данные в Python профессионально. Python использует алгоритм Timsort — гибридный алгоритм, сочетающий сортировку вставками и сортировку слиянием. Его сложность в среднем и худшем случае составляет .
В Python есть два основных способа сортировки:
1. Метод list.sort()
Этот метод сортирует список in-place (на месте). Это означает, что исходный список изменяется, и новый список не создается. Это экономит память.
2. Функция sorted()
Эта функция создает и возвращает новый отсортированный список, оставляя исходный без изменений. Это удобно, если вам нужно сохранить оригинальный порядок данных.
Параметры сортировки
Оба инструмента (sort и sorted) поддерживают мощные параметры:
* reverse=True: сортировка по убыванию.
* key: функция, которая применяется к каждому элементу перед сравнением. Это позволяет сортировать сложные объекты.
Пример сортировки строк по их длине, а не по алфавиту:
!Визуализация работы параметра key при сортировке
Устойчивость сортировки (Stability)
Встроенная сортировка в Python является устойчивой (stable). Это важное понятие в теории алгоритмов.
> Устойчивая сортировка не меняет взаимный порядок элементов, имеющих одинаковые ключи сравнения.
Если у вас есть список студентов, отсортированный по имени, и вы затем сортируете его по оценкам, устойчивая сортировка гарантирует, что студенты с одинаковыми оценками останутся упорядоченными по имени. Неустойчивая сортировка может перемешать их случайным образом.
Заключение
Сегодня мы заложили фундамент. Мы узнали, что эффективность алгоритмов измеряется через О-нотацию, и что — это золотой стандарт для сортировок общего назначения. Мы также познакомились с мощными встроенными инструментами Python.
В следующей статье мы перейдем к практике и разберем, возможно, самый известный (хоть и не самый эффективный) алгоритм — Сортировку пузырьком (Bubble Sort). Мы напишем его с нуля, проанализируем его сложность и попробуем оптимизировать.