Сложность алгоритмов

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

Обычно у алгоритмов бывает две сложности:

1. Временная сложность — как количество операций, которые выполняются при работе алгоритма, связано с объёмом входных данных.

2. Сложность по памяти — как количество памяти, которое нужно алгоритму, связано с размером входных данных.

Некоторые виды сложности алгоритмов:

• O(n) — линейная сложность. Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве.

• O(log n) — логарифмическая сложность. Простейший пример — бинарный поиск.

• O(n2) — квадратичная сложность. Такую сложность имеет, например, алгоритм сортировки вставками.

• O(1) — время работы алгоритма вообще не зависит от размера входных данных. Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз.

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