Алгоритмы и структуры данных
July 27, 2021

Немного про сложность алгоритмов

Здесь напишу самый минимум про тему, что зачастую вызывает панику у новичков.

Виды сложности алгоритмов

О (на самом деле омикрон, но в народе прижилось Big-O) - верхняя граница вычислительной сложности.

Ω (омега) - нижняя граница вычислительной сложности.

Θ (тета) - подразумевает, как О, так и Ω. Алгоритм имеет сложность Θ(N), когда он одновременно обладает сложностью О(N) и Ω(N), то есть определяет точную границу сложности.

Кроме этого встречал еще определение пространственной сложности.

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

На собеседованиях, как правило, вопросы про Ω, Θ и пространственную сложность даже не задают. Поэтому дальше подробнее только про Big-O.

Я встречал различные определения Big-O. Приведу примеры:

Идея Big-O - показать сколько шагов должна сделать машина, чтобы закончить выполнение алгоритма, независимо от ее производительности.
Big-O - показывает верхнюю границу зависимости между выходными параметрами функции и количеством операций, которые выполнит процессор. Big-O описывает скорость роста.

Виды сложности алгоритмов Big-O

По убыванию эффективности:

сложность Big-o по убыванию эффективности

Как начать учиться считать сложности алгоритмов?

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

  1. Макдауэлл - "Карьера программиста"
  2. Бхаргава - "Грокаем алгоритмы"

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