Данным постом хочу заложить начало для серии статей, посвященных изучению алгоритмов и структур данных, дабы залатать (хотя бы кое-как) брешь в собственных знаниях на этот счет.

Изучать буду по книге Кормена, в связи с чем, в статьях будет приводиться мой вольный пересказ вышеупомянутой книги, а местами будут проскакивать целые цитаты из нее. Однако код будет авторским (ну на сколько это возможно в нашем мире копипасты).

Публикуемые статьи не является полноценным материалом для обучения, и не заменяют собой книги-первоисточника.

Первая статья посвящается общим терминам и понятиям.

  1. Введение
  2. Оценка временной сложности алгоритма
  3. Оценка пространственной сложности алгоритма
  4. Подходы к выбору подходящего алгоритма
  5. Резюме

1. Введение

Компьютерный алгоритм (далее просто алгоритм) — набор шагов для решения какой-либо вычислительной задачи.

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

  1. алгоритм должен КОРРЕКТНЫМ. Т.е. ВСЕГДА давать правильное решение поставленный задачи, при тех же входных данных;
  2. алгоритм должен использовать вычислительные ресурсы машины ЭФФЕКТИВНО.

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

Алгоритм, который дает правильное решение, но требующий бОльшего времени для получения этого самого решения — не имеет практической ценности.

Мерой эффективности использования вычислительных ресурсов, тем или иным алгоритмом, является его пространственная и временнАя сложность.

ВременнАя сложность — функциональная зависимость времени работы алгоритма от размера входных данных. Пространственная сложность — функциональная зависимость объема задействованной (на работу алгоритма) памяти от размера входных данных.

2. Оценка временной сложности алгоритма

При определении функции временной сложности делается несколько упрощений о том, сколько времени занимают простые операции. Принято считать, что каждая "простая" операция: арифметическая, сравнения, присваивания, получения значений элемента массива по индексу, получения значения по ключу из хэш-таблицы, вызов процедуры (а также возврат значения из нее) — выполняются за некое константное время, не зависящее от размера входных данных. Также, для оценивания скорости работы алгоритма, используется только ПОРЯДОК роста функции. Иными словами, учитывается ТОЛЬКО ДОМИНИРУЮЩИЙ ЧЛЕН ФУНКЦИИ, без учета коэффициентов и свободных членов.

Для оценки временной сложности алгоритмов используют следующие асимптотические (при стремлении размера входных данных к бесконечности) функции: θ(n) (тета от n), O(n) (О-большое от n), o(n) (о-малое от n), Ω(n) (омега-большое от n) и ω(n) (омега-малое от n).

O(n) — верхняя асимптотическая оценка роста временной функции (наихудший случай). Смысл оценки — меньше или равно (<=).

o(n) — строгая верхняя асимптотическая оценка роста временной функции (наихудший случай с отбрасыванием всех второстепенных членов функции). Смысл оценки — строго меньше (<).

Ω(n) — нижняя асимптотическая оценка роста временной функции (наилучший случай). Смысл оценки — больше или равно (>=).

ω(n) — строгая нижняя асимптотическая оценка роста временной функции (наилучший случай). Смысл оценки — строго больше (>).

θ(n) — нижняя и верхняя асимптотические оценки роста временной функции (точная оценка). Смысл оценки — равно (=).

Наиболее востребованной оценкой временной сложности является O(n), смысл которой показать, что данный алгоритм работает "НЕ ХУЖЕ ЧЕМ" <определенная функциональная зависимость>.

Основные виды функциональной зависимости при асимптотической аппроксимации O(n):

  1. O(1) — константная;
  2. O(logn) — логарифмическая;
  3. O(n) — линейная;
  4. O(nlogn) — линейно-логарифмическая;
  5. O(n^2) — квадратичная;
  6. O(2^n) — степенная;
  7. O(n!) — факториальная.

В качестве демонстрации подхода к оценке временной сложности, рассмотрим функции "линейного поиска" элемента в массиве.

Процедура: linear_search(A, n, x)

Ввод:

  • A: массив;
  • n: количество элементов массива A;
  • x: значение, которе требуется найти в массиве A.

Вывод: любой индекс i, для которого A[i] = x, либо специальное значение NOT_FOUND, которое может представлять собой отрицательное число, означающее, что искомый элемент в массиве не найден.

NOT_FOUND = -1

def linear_search(A, n, x):
    answer = NOT_FOUND

    for i in range(n):
        if A[i] == x:
            answer = i

    return answer

Данный алгоритм поиска не является эффективным, здесь он приведен исключительно для демонстрации подхода к оцениванию временной сложности алгоритма.

Разобьем функцию на шаги (помним, что алгоритм — это набор ШАГОВ).

def linear_search(A, n, x):
    answer = NOT_FOUND [1]

    for i in range(n): [2]
        if A[i] == x:  [3]
            answer = i [4]

    return answer      [5]

Выше уже мы определились, что время выполнения простых операции (арифметические, присваивание, вызов функции, возврат значения из функции, получение элемента массива по индексу и т.д.) принято считать за константное, поэтому на шаге [1] время выполнения инструкции будет неким константным временем t1, на шаге [2] цикл for выполнит присваивание значения переменной i а также проверку на выход за границы массива n + 1 раз (+1 один как раз для проверки, что массив закончился), итого для шага [2] получим время — t2 * (n + 1). Шаг [3] — проверка для каждого элемента массива, т.е. — t3 * n. Шаг [4] просто присваивание если условие на шаге [3] дало True (что может случиться только один раз), поэтому шаг [4] — это просто одиночное присваивание, т.е. константа t4. Шаг [5] — возврат значения из функции, т.е. еще одна константа t5.

После анализа имеем:

def linear_search(A, n, x):
    answer = -1        [t1]

    for i in range(n): [t2*(n+1)]
        if A[i] == x:  [t3*n]
            answer = i [t4*n]

    return answer      [t5]

Рассчитаем временную сложность наихудшего (O(n)) сценария работы, т.е. такого, когда искомое значение x находится в самом конце списка A.

f(n) = O(t1 + t2*(n+1) + t3*n + t4*n + t5)

Приведя подобные слагаемые, получаем:

f(n) = O((t2 + t3+ t4) * n + (t1 + t5))

Данное уравнение можно упростить до:

f(n) = O(An + B), где A и B — некоторые константы.

Отбрасывая коэффициент A и свободный член B (так как в асимптотическом приближении, они не играют роли), получим:

f(n) = O(n)

Итого, временная сложность данного алгоритма поиска свелась к линейной функции — O(n). Это означает, что время поиска линейно зависит от размера входного массива. К примеру, для поиска элемента в массиве из одного этого элемента, алгоритм затратит 1 единицу некоторого кванта времени. Тогда как для поиска в массиве из 1_000_000 элементов, если искомый элемент находится в конце списка (наихудший случай), время работы алгоритма составит 1_000_000 временнЫх единиц.

Казалось бы — арифметика. Однако на практике, рассчитать таким образом временную сложность реального кода гораздо сложнее, ведь для этого потребуется оценить сложность всех входящих в код функций. Для такого рода задач применяют подход, называемый — инвариантом цикла. Но данный способ расчета временной сложности очень громоздкий, и является уделом академического круга или же, скажем, специалистов ~~Роскосмоса~~ НАСА. Для наших быдлокодерских задач важно научиться "прикидывать в уме", потенциальную сложность, и этого будет достаточно.

3. Оценка пространственной сложности алгоритма

Разные структуры данных, и разные операции над ними требует выделения разного объема RAM, что в свою очередь может послужить фактором определяющим использование того или иного алгоритма, в зависимости от выбранных структур.

Считается пространственная сложность также, как и временнАя, но только смотрят не на такты, а на выделенный на алгоритм объем памяти. Подсчитывают все аллокации: каждую переменную (в том числе и аргументы функций на стеке) для каждого вызова функции по всей глубине вызовов, каждую ячейку массива как отдельную переменную. И, также как с оценкой временной сложности, для оценки пространственной сложности, при асимптотическом приближении, отбрасываются константы и члены низших порядков.

Пример для linear_search в среде Python3.12 (контейнер для целочисленной переменной аллоцирует 28 байт памяти по умолчанию):

def linear_search(A, n, x) [28n + 28 + 28]:
    answer = -1        [+28]

    for i in range(n): [+28*(n+1)]
        if A[i] == x:  [+0]
            answer = i [+0]

    return answer      [+0]

f(n) = 28n + 28 + 28 + 28 + 28*(n+1) = 56n + 112 байт.

В асимптотическом приближении, остается просто n. Стало быть, пространственная сложность функции линейного поиска — O(n) [совпадает с временной сложностью].

Опять же, нам такой построчный анализ делать не требуется, а требуется уметь "на глаз" определять сколько может сожрать памяти тот или иной код, с учетом особенностей ЯП и используемых в коде структур. Если не удается быстро прикинуть в уме, то на помощь приходят инструменты профилирования и средства, наподобие сишной sizeof() (для python можно использовать __size__() либо sys.getsizeof()).

4. Подходы к выбору подходящего алгоритма

Анализ размера данных.

Размер входных данных является ключевым фактором при выборе алгоритма. Для малых объемов данных более простые алгоритмы могут быть более эффективными, даже если их теоретическая сложность выше. Например, сортировка вставками может быть быстрее на небольших массивах, чем, например, быстрая сортировка (quick sort), которая хорошо себя показывает именно на массивах большого размера.

Учет худшего, среднего и лучшего случая.

Различные алгоритмы имеют разные характеристики производительности в зависимости от данных. Например, сортировка быстрым методом (quick sort) в среднем случае имеет сложность O(n log n), но в худшем случае — O(n²). Понимание этих различий помогает выбрать наиболее подходящий алгоритм.

Ресурсные ограничения.

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

Тестирование и профилирование.

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

Читаемость и поддержка.

Иногда более простой и понятный алгоритм предпочтительнее сложного, даже если он простой работает медленнее. Читаемость и легкость сопровождении кода также являются важными факторами, если время работы простого алгоритма приемлемо для конкретной задачи.

5. Резюме

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

Выбор подходящего алгоритма это сочетание: теоретических знаний о временной и пространственной сложности; практического опыта, учитывающего специфику программных средств (ЯП, интерпретатор/компилятор, фреймворк, библиотека, протокол и т.д.); учитывание потенциала к изменениям, особенностей задачи и проекта в целом.