Понять Big O раз и навсегда

• 
  — Константное время. Представьте, что вы скачиваете фильм по прямой ссылке, чтобы посмотреть его вечером. Само действие «получить доступ к файлу» занимает фиксированное время. И совершенно неважно, посмотрите вы этот фильм один раз, десять или сто — на процесс скачивания (получения данных) это никак не повлияет. Время на выполнение задачи всегда одинаковое и не зависит от ваших дальнейших аппетитов.
  
• 
  — Линейное время. А теперь вы решили прочитать книгу. Если в ней 100 страниц, вы справитесь за пару вечеров. Если 1000 страниц — уйдет пара недель. Время, которое вы потратите, растет строго пропорционально объему книги. Данных (страниц) стало в 10 раз больше — времени потребовалось в 10 раз больше. Это и есть линейный рост.

— Константное время

def get_first_element(items):
    return items[0] # Мы сразу берем то, что нужно.

— Логарифмическое время: Разделяй и властвуй

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

— Линейное время: Честный трудяга

def find_max(items):
    max_val = items[0]
    for item in items: # Проходим по всему массиву от начала до конца
        if item > max_val:
            max_val = item
    return max_val

— Линейно-логарифмическое время: Быстрые сортировки

— Квадратичное время: Убийца серверов

def bubble_sort(items):
    n = len(items)
    for i in range(n):
        for j in range(n - i - 1): # Вложенный цикл!
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]

и

— Экспонента и факториал: “Всё плохо, переписываем”

def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2) # Вызываем функцию дважды на каждый шаг

• Два цикла подряд =
  
  . Если вы сначала прошлись по массиву A, а затем (независимо) по массиву B, время выполнения складывается. Называть это
  
  — ошибка, потому что массивы могут быть совершенно разных размеров.
  
• Вложенные циклы =
  
  . Если цикл по массиву B находится внутри цикла по массиву A, мы умножаем. Для каждого элемента из A мы полностью пробегаем массив B. Если в A 100 элементов, а в B 100 000, алгоритм сделает 10 миллионов шагов.

• Плохо (Space
  
  ): Вы создаете внутри функции новый пустой массив, проходитесь циклом по старому с конца в начало и копируете элементы в новый. Вы только что удвоили потребление памяти. Если исходный массив весил 1 ГБ, ваш скрипт попросит у системы еще 1 ГБ.
  
• Хорошо (Space
  
  ): Вы делаете это алгоритмом In-place («на месте»). Вы берете первый и последний элементы текущего массива и просто меняете их местами, сдвигаясь к центру. Вам понадобилась всего одна дополнительная переменная для временного хранения значения при обмене. Сколько бы данных ни было — 10 штук или 10 миллионов — алгоритм потребует фиксированный минимум памяти.

• Система выделяет где-то в памяти новый кусок, обычно в 2 раза больше старого.
  
• Программа берет все существующие элементы и по одному переносит их в новый массив.

• Нет циклов и рекурсий? Поздравляю, скорее всего, это
  
  .
  
• Один цикл (или несколько, но друг за другом)? Это
  
  . Всё хорошо, алгоритм масштабируется предсказуемо.
  
• Цикл внутри цикла по одним и тем же данным? Это
  
  . Внимание, красная тревога! Если данных будет больше пары тысяч, начнутся тормоза.
  
• Используете встроенные методы сортировки? Заложите в уме сложность
  
  .
  
• Используете операторin(илиcontains) внутри цикла? Помните: поиск по массиву (list) — это скрытый цикл, то есть
  
  . Если завернуть его в ваш цикл, получите
  
  . Поиск по хэш-таблице (dict или set) — это
  
  . Замена массива на множество часто спасает продакшен!
  
• Константы? Отбрасываем.
  
  — это всё тот же
  
  . Смотрите только на самое «узкое» место алгоритма.