Какой алгоритм называют линейным?

Алгоритмом называют линейным, если время его выполнения и/или количество операций пропорционально объёму входных данных. То есть, если объём входных данных увеличивается в два раза, то и время выполнения (или число шагов) также увеличивается примерно в два раза. Обозначается такая сложность как O(n), где n — количество элементов во входных данных.

Пример линейного алгоритма — поиск максимального числа в массиве. Чтобы найти максимум, нужно просмотреть каждый элемент массива хотя бы один раз. Если в массиве 10 элементов, алгоритм выполнит 10 сравнений; если 100 — 100 сравнений. Таким образом, затраты ресурсов растут линейно с увеличением входа.

Характерные черты линейных алгоритмов:

• один проход по данным;

• нет вложенных циклов, проходящих по тем же данным;

• шаги алгоритма не зависят от структуры данных, а только от их количества.

Примеры задач с линейными алгоритмами:

• подсчёт суммы всех элементов массива;

• поиск минимального/максимального значения;

• проверка, содержит ли массив определённый элемент (линейный поиск).

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