Как с тобой сложно: Говорим о временной сложности алгоритмов

Это длинный гайд для начинающих разработчиков, который призван помочь разобраться в теме временнóй сложности и O(n) с нуля и научиться оценивать сложность своих алгоритмов. Я надеюсь, он получился максимально полным и понятным. Комментарии и отзывы принимаются под текстом.

Что такое временная сложность

Время выполнения алгоритма обычно зависит от размера данных, которые он получил на вход, чтобы обработать. С увеличением количества этих данных обычно увеличивается и время, которое нужно алгоритму для выполнения своей задачи. Временная сложность - это способ оценить эту взаимосвязь, чтобы понять, как время, затраченное кодом, зависит от объема входных данных.

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

Большое O (Big O notation) - это простой способ математически описать, сколько напитков вам понадобится в зависимости от количества гостей. Это поможет вам понять, как количество напитков увеличивается по мере того, как растет список приглашенных.

Например:

• Если вам нужно одинаковое количество напитков независимо от n, мы говорим, что у такого алгоритма сложность O(1), или "постоянное время выполнения".
• Если нужное количество напитков прямо пропорционально количеству гостей, мы говорим, что у алгоритма сложность O(n), или "линейное время" (например, один напиток на гостя или два напитка). Даже если напитков по два на одного человека - мы все равно пишем O(n), а не O(2n), потому что нас интересует так называемая "асимптотическая сложность": когда число гостей стремится к бесконечности, и число напитков растет прямо пропорционально ему, нам уже не важно, сколько выпьет каждый. Важно, что зависимость линейная.
• Если вы состоите в странном культе, где каждый гость должен напоить каждого другого гостя, вы должны принести по n напитков на каждого из n человек. У такого алгоритма сложность была бы квадратичная - O(n²).

При анализе временной сложности бывает полезно рассмотреть три сценария работы: наилучший, средний и наихудший:

1. Наилучший случай: Это минимальное количество времени, которое требуется алгоритму для выполнения, при наиболее благоприятных входных данных. Например, когда гости напились перед приходом.
2. Средний случай: Представляет собой самое вероятное время работы алгоритма среди всех возможных входов. Оно часто более информативно, чем лучший или худший случай, так как дает более реалистичную оценку производительности.
3. Наихудший случай: Это максимальное количество времени, которое требуется алгоритму для выполнения, учитывая наименее благоприятные входные данные. Анализ наихудшего случая помогает определить верхнюю границу времени работы и гарантирует, что оно не превысит определенного порога в любой ситуации.

Как оценить сложность алгоритма

Во-первых, начните с определения базовых операций, которые выполняет код, таких как арифметические операции, сравнение и присваивание. Эти операции составляют основу вашего алгоритма. Например:

result = a + b  # базовая арифметическая операция 
if a > b:       # базовая операция сравнения
    #...

Затем нужно подсчитать частоту операций, то есть понять, как часто происходит каждая базовая операция относительно размера данных (n).

Первое, что стоит сделать, это проанализировать циклы: Циклы существенно влияют на временную сложность. Одиночный цикл обычно имеет сложность O(n). Двойной вложенный цикл - O(n²).

for i in range(n):      # Внешний цикл: O(n) 
    for j in range(n):  # Внутренний цикл: O(n) 
        #...            # Суммарная сложность: O(n^2)

Далее нужно рассмотреть условные операторы: Оцените временную сложность каждой ветви в условных операторах (if-else, switch) и выберите ветвь с самой высокой сложностью (т.е. наихудший сценарий).

def get_max(nums):
    if not nums:  # O(1)
        return None
    else:         # O(n) (один цикл)
        max_num = nums[0]
        for num in nums: 
            if num > max_num:
                max_num = num 
        return max_num 

В приведенном примере мы считаем, что функция имеет временную сложность O(n), т.к. не принимаем во внимание маловероятный лучший сценарий - когда список nums пуст.

Наконец, вы можете проанализировать рекурсивные вызовы: Это сложнее, но если вам интересно погрузиться в тему, вы можете почитать об основной теореме о рекуррентных соотношениях.

После того как вы проанализировали сложность различных последовательных частей вашего кода, вы можете объединить их. Просто выберите самую высокую. Например:

def example_function(arr):
    # Один цикл: O(n)
    for i in range(len(arr)):
        print(arr[i])

    # Вложенный цикл: O(n^2)
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])

    # Условный оператор: O(n) (в худшем случае)
    if len(arr) % 2 == 0:
        for i in range(len(arr)):
            print(arr[i])
    else:
        print("Odd length array")

В данном примере у нас есть три отрывка кода:

1. Одиночный цикл с временной сложностью O(n).
2. Вложенные циклы с временной сложностью O(n²).
3. Условный оператор с временной сложностью O(n) в худшем случае.

Чтобы объединить эти сложности, мы выбираем самую высокую. Таким образом, функция example_function имеет временную сложность O(n²).

Операции над популярными структурами данных

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

Легенда для таблицы ниже:

• Чтение означает получение элемента по индексу или ключу.
• Поиск - нахождение индекса или ключа элемента по его значению (для этого нужно определенным образом обойти структуру данных).
• Вставка - добавление нового элемента по заданному индексу или ключу
• Удаление - говорит само за себя

В этой таблице мы используем новое обозначение сложности, которое не упоминали раньше - O(log n) - это логарифмическая сложность. Как правило, под основанием логарифма в большой O всегда подразумевают двойку. Чтобы понять, что обозначает логарифмическая сложность - изучите алгоритм бинарного поиска. Суть этой сложности в том, что мы с каждым шагом алгоритма делим количество оставшейся работы пополам.

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

На самом деле, знать алгоритмы сортировки и их временные сложности не так важно. Выбирать алгоритм и тем более реализовывать его в работе вам, скорее всего, не придется, т.к. в стандартных библиотеках уже реализованы state-of-art алгоритмы. Но без сортировки статья была бы неполной, тем более, что об этом могут спросить на интервью.

Существует несколько алгоритмов, которые считаются самыми оптимальными, и их объединяет одно - в среднем случае они дают сложность O(n log n) - то есть n, помноженный на логарифм. Это предел, который можно ожидать от алгоритма сортировки в среднем случае.

Вот несколько таких оптимальных алгоритмов:

• Сортировка слиянием: Рекурсивно делит массив пополам, сортирует каждую половину, а затем объединяет их.
• Быстрая сортировка: Выбирает "опорный" элемент, разбивает остальные элементы на две группы: те, которые меньше опорного, и те, которые больше. Затем рекурсивно сортирует обе группы.
• Сортировка кучей: Складывает элементы массива в двоичную кучу, затем по одному извлекает элемент из верхушки кучи обратно в массив.
• Timsort: Гибрид из сортировки слиянием и сортировки вставкой, адаптированный для эффективной работы с реальными данными. Это алгоритм используется в Python.

Кроме того, программистам преподают несколько неоптимальных (как правило, O(n²)), но более простых для понимания алгоритмов:

• Пузырьковая сортировка: Многократно проходит по массиву, сравнивает соседние элементы и располагает их в правильном порядке. И так до тех пор, пока массив не окажется отсортирован.
• Сортировка выбором: Делит массив на отсортированную и неотсортированную области. Многократно выбирает наименьший элемент из неотсортированной области и перемещает в конец отсортированной области.
• Сортировка вставками: По одному вставляет элементы из неотсортированной области массива в нужное место в отсортированной области.
• Сортировка перемешиванием: Разновидность пузырьковой сортировки, которая просматривает список в обоих направлениях: поочередно слева направо, потом справа налево.
• Гномья сортировка: Похожа на сортировку вставкой, но с несколько иным подходом. Продвигается вперед по списку, и если соседние элементы в неправильном порядке, меняет их местами и делает шаг назад.

Пространственная сложность (затраты по памяти)

Под пространственной сложностью понимается объем памяти, используемый алгоритмом, а под временной сложностью - время его выполнения. Эти два фактора часто взаимосвязаны: оптимизация одного из них может привести к увеличению другого. Поэтому в работе часто проходится находить компромисс между затратами на одно и на другое.

Что полезно знать?

• Выбранные вами структуры данных и алгоритмы могут существенно повлиять на баланс между пространством и временем. Некоторые структуры данных потребляют больше памяти, но позволяют выполнять нужные операции быстрее, в то время как другие могут щадить память, но работать медленнее.
• Кэширование и мемоизация могут использоваться для снижения временной сложности за счет хранения в памяти результатов предыдущих вычислений. Они могут ускорить алгоритм, но под кэш нужно место.
• Сжатие данных может уменьшить пространственную сложность. Однако процессы сжатия и разжатия будут отнимать время на выполнение.

Иногда временная сложность - не самое главное

Не стоит чрезмерно беспокоиться о временной сложности. Оптимизация кода - это полезно, но при этом важно не ставить под угрозу его читаемость и удобство сопровождения. Вы можете дооптимизировать код так, что он будет выполняться быстро, но вносить правки в него будет тяжело. Он больше не будет читаться как правила человеческой бизнес-логики, а как тонко сформулированное заклинанение для машины. Старайтесь найти баланс между оптимизацией и качеством кода.

Кроме того, современные компиляторы уже обладают способностью применять некоторые оптимизации во время сборки. Это такие оптимизации как устранение мертвого кода, разворачивание циклов, инлайнинг функций и др. Ваш компилятор уже оптимизирует код за вас, чтобы вы сфокусировались на решении бизнес-задач.

Помните еще кое-что. Если ваш код включает достаточно много операций ввода-вывода (например, чтение файлов, прием сетевых соединений или запросы к базе данных), узким местом (то есть местом, которое выполняется дольше всего) чаще всего будет ввод-вывод, а не ваш код. Данные обычно пишутся на диск или передаются по сетевым соединениям гораздо медленнее, чем ваш код выполняется на процессоре.

О чем еще погуглить

• Оптимизации, применяемые компиляторами. Например, упомянутые выше: удаление мертвого кода, разворачивание циклов и инлайнинг функций. А также сворачивание констант, оптимизация хвостовой рекурсии (tail call optimization), удаление общих подвыражений, векторизация (SIMD).
• Параллельные и распределенные вычисления: Алгоритм может быть адаптирован для одновременного выполнения на нескольких процессорах, что уменьшает общее время выполнения. Крупные приложения часто используют такой подход: это называется горизонтальным масштабированием.
• Профилирование и бенчмаркинг: Чтобы определить реальную производительность вашего кода, используйте профайлеры и утилиты бенчмаркинга. Эти инструменты помогут вам разобраться, какие части вашего кода работают хуже всего.

Материал подготовлен с ❤️ редакцией Кухни IT.