Что такое линейная сложность

Линейная сложность (O(n)) означает, что время выполнения алгоритма растёт пропорционально размеру входных данных. Если количество операций увеличивается прямо пропорционально n, то алгоритм имеет линейную сложность.

Пример с циклом, который перебирает все элементы списка:

def print_elements(arr):
    for element in arr:  # O(n) — зависит от длины arr
        print(element)

Характеристики:

• Время выполнения прямо зависит от размера данных
• График — прямая линия
• Примеры: поиск в неотсортированном массиве, подсчёт суммы элементов

Важно: даже если есть несколько последовательных циклов (O(n) + O(n)), сложность остаётся линейной (O(n)), так как константы в нотации О-большое отбрасываются.