Что означает линейная сложность?

Линейная сложность (O(n))

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

Определение и нотация

В нотации Big O линейная сложность обозначается как O(n), где:

• O — оценка верхней границы
• n — размер входных данных (количество элементов, символов, строк и т.д.)

Время выполнения: T(n) = c × n + d, где c и d — константы, зависящие от конкретной операции.

Примеры алгоритмов с O(n)

Линейный поиск — самый простой пример:

def linear_search(arr, target):
    """Ищет элемент в массиве. Сложность O(n)"""
    for i in range(len(arr)):  # Цикл выполняется n раз
        if arr[i] == target:
            return i
    return -1

# Если массив из 1000 элементов — до 1000 сравнений
# Если массив из 2000 элементов — до 2000 сравнений

Подсчет сумы элементов:

def sum_elements(arr):
    """Подсчитывает сумму всех элементов. O(n)"""
    total = 0
    for num in arr:  # Проходим через каждый элемент один раз
        total += num
    return total

Копирование массива:

def copy_array(arr):
    """Создает копию массива. O(n)"""
    result = []
    for item in arr:  # n операций
        result.append(item)
    return result

# Альтернатива: O(n) все равно
result = arr.copy()  # Также O(n) — копирование занимает линейное время

Сравнение с другими сложностями

Чтобы понять, почему O(n) важна, сравню с другими:

Почему O(n) считается приемлемой

Для большинства приложений O(n) — это хороший стандарт:

• Алгоритм масштабируется предсказуемо
• Даже для миллионов элементов работает за разумное время
• Легче оптимизировать (константные множители)

С другой стороны, O(n²) при 10000 элементов уже дает 100 млн операций.

Частые ошибки и важные нюансы

Ошибка 1 — путанница между O(n) и полным временем выполнения:

def process_data(arr):
    # O(1) — инициализация
    result = {}
    
    # O(n) — основной цикл
    for item in arr:
        result[item] = True
    
    # O(1) — возврат
    return result

# Итоговая сложность: O(n), не O(n) + O(1) = O(n)
# Константные операции игнорируются в Big O

Ошибка 2 — вложенные циклы это O(n²), не O(n):

# НЕПРАВИЛЬНО
for i in range(n):      # O(n)
    for j in range(n):  # O(n)
        print(i, j)     # O(n²) — n × n операций!

Реальные примеры из Python

# O(n) операции в Python
arr = [1, 2, 3, 4, 5]

sum(arr)              # O(n) — проходит через все элементы
max(arr)              # O(n) — нужно сравнить все
arr.count(3)          # O(n) — проходит весь список
val in arr            # O(n) — в худшем случае проверяет все
arr.sort()            # O(n log n) — сортировка быстрее чем O(n²)
3 in my_set           # O(1) — множество ищет за константное время!

Практический совет

Когда вы видите один цикл через данные — это, скорее всего, O(n). Когда видите вложенные циклы — это обычно O(n²) или хуже. Для собеседований важно:

1. Уметь анализировать сложность своего кода
2. Знать, когда O(n) — это хорошо, а когда нужно лучше
3. Оптимизировать с помощью структур данных (sets, dicts вместо списков)

У опытного разработчика это входит в мышление на уровне рефлекса.