20 ноя 2024

Сложность алгоритмов: глубокий разбор O(log n)

10 мин

Разберем сложность алгоритмов, уделив особое внимание O(log n): что означает этот тип сложности, как его определить и оценить, а также почему он имеет решающее значение для оптимизации производительности алгоритмов.

Сложность алгоритма — это показатель, который характеризует его производительность. В этой статье будет подробно рассмотрена временная сложность алгоритмов O(log n): что это такое, когда возникает и как помогает решать задачи оптимальным способом.

Основные типы сложности алгоритмов

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

Типы сложности алгоритмов:

константная, O(1). В таком случае время выполнения не зависит от объема входных данных: алгоритм всегда выполняется за одинаковое количество операций. Простой пример — функция сложения двух чисел:

def add_numbers(a, b):
   return a + b

линейная, O(n). Время выполнения увеличивается пропорционально объему входных данных, то есть растет линейно: если объем увеличивается в 5 раз, то время выполнения тоже пятикратно увеличивается. Классический пример — поиск минимального значения:

def get_min_item(arr):

    min = arr[0]

    for i in range(1, len(arr)):

        if min > arr[i]:

            min = arr[i]

    return min

логарифмическая, O(log n). Такие алгоритмы уменьшают объем данных для обработки на каждой итерации. Время работы логарифмических алгоритмов растет медленно относительно увеличения объема входных данных, поэтому их относят к эффективным. Пример — бинарный поиск в отсортированном массиве, когда на каждой итерации количество элементов, которые нужно обработать, уменьшается в 2 раза. Подробнее бинарный поиск будет рассмотрен далее.
линейно-логарифмическая, O(n log n). Возникает, когда в алгоритме комбинируется перебор всех элементов и уменьшение их количества на каждой итерации, например, как в алгоритме сортировки слиянием. По эффективности такие программы располагаются между линейной и квадратичной сложностью.
квадратичная, O(n2). Время работы зависит от квадрата объема входных данных, квадратичная сложность свойственна некоторым алгоритмам сортировки, например, сортировка пузырьком:

def bubble_sort(arr):

    n = len(arr)

    for i in range(n):

        for j in range(0, n-i-1):

            if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]

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

факториальная, O(n!). Это наименее эффективные алгоритмы: их скорость быстро падает с увеличением объема входных данных. Если n = 2, то количество операций тоже равно 2, а если n = 10, то количество операций составит уже 3628800. Примером служит перебор всех возможных комбинаций элементов массива:

from itertools import permutations

arr = [1, 2, 3]

perm = list(permutations(arr))

print(perm)

# Вывод

# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Big O Notation: инструмент для оценки производительности

Прежде чем рассмотреть Big O Notation, стоит сказать о том, что в программировании выделяют три случая работы алгоритмов: худшая (worst case), средняя (average case) и лучшая (best case):

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

Big O Notation — это инструмент, который используется для оценки и анализа скорости алгоритмов в программировании. Другими словами, Big O Notation описывает то, как меняется эффективность работы программы в зависимости от объема входных данных. Так, эта нотация позволяет сравнивать алгоритмы между собой в контексте их производительности и выбирать оптимальный вариант, а также прогнозировать масштабируемость программы. Big O Notation описывает верхнюю границу времени выполнения алгоритма (худший случай): если в большинстве ситуаций он выполняется быстро, но существуют случаи, когда эффективность снижается, описываться будет именно этот случай.

Также Big O Notation может использоваться для оценки сложности алгоритма по памяти — этот показатель тоже стоит учитывать во время проектирования, так как некоторые программы оптимальны по времени выполнения, но неэффективны по количеству потребляемых ресурсов.

Помимо Big O существуют и другие нотации:

Big Omega — описывает нижнюю границу времени выполнения (лучший случай);
Big Theta — нужна для описания среднего случая.

Логарифмическая сложность O(log n): применение и примеры

Что означает O(log n) и в каких ситуациях она появляется

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

Примеры алгоритмов с логарифмической сложностью

Классический пример таких алгоритмов — это бинарный поиск:

def binary_search(arr, number):

    left = 0

    right = len(arr) - 1

    while left <= right:

        mid = (left + right) // 2

        if arr[mid] == number:

            return mid  

        elif arr[mid] < number:

            left = mid + 1

        else:

            right = mid - 1

    return -1

array = [1, 3, 5, 7, 9, 11, 13, 15]

print(binary_search(array, 9))

# Вывод: 4

Рассмотрим, как он работает и почему имеет логарифмическую сложность:

Имеется отсортированный массив, содержащий 8 элементов (n = 8): [1, 3, 5, 7, 9, 11, 13, 15]. Нужно найти элемент со значением 9.
Далее указываются границы поиска: индексы первого — 0 и последнего элементов массива — len(arr) - 1.
Поиск среднего индекса (mid = (left + right) // 2). В данном случае mid = (0 + 7) // 2. В результате получаем mid = 3, а 3 — это индекс значения 7.
Полученное значение (в коде это arr[mid]) сравнивается с искомым: 7 < 9, а значит, искомый элемент расположен в правой части массива — левую можно не рассматривать.
Значение левой границы поиска меняется: left = mid + 1, теперь индекс элемента на этой границе равен 4 (правая граница остается такой же).
Новый mid = (4 + 7) // 2 = 5, элемент с индексом 5 — это 11. 11 > 9, значит, искомый элемент расположен в левой части.
На этом шаге левой границей поиска является элемент массива с индексом 4, а правая граница меняется: right = mid - 1 = 5 - 1 = 4. 4 — это и есть индекс искомого значения 9, он найден. Поиск завершился за 3 итерации.

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

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

если искомое значение меньше текущего, то правое поддерево отбрасывается;
если искомое больше текущего, то отбрасывается левое поддерево.

Работа программы будет продолжаться, пока не будет найден нужный элемент, либо пока не закончатся узлы для проверки.

Сравнение O(log n) с другими типами сложности

Алгоритмы со сложностью O(log n) уступают по эффективности только программам, у которых этот показатель равен O(1), так как в них скорость работы не зависит от количества переданных данных. Однако константная сложность встречается нечасто, поэтому обычно программы с логарифмической сложностью считаются наиболее эффективным вариантом.

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

Наглядно рассмотреть разницу между различными типами сложности можно на графике.

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

Big O Notation подразумевает асимптотическую оценку сложности: из этого следуют некоторые правила. Во-первых, константные множители не учитываются — объем входных данных оказывает несущественное влияние на эти компоненты формулы. Например, такая запись O(n2+5n+3) приравнивается к временной сложности O(n2).

Во-вторых, если выражение содержит сумму, учитывается то слагаемое, которое растет быстрее других, например, O(n2 + 2n) = O(n2).

Первый метод оценки сложности алгоритмов не предполагает проведение серьезного математического анализа программистом: он основан на анализе структуры программы. Рассмотрим на примерах.

Ниже представлен алгоритм линейного поиска — если нужное значение найдено, то цикл прерывается:

def linear_search(arr, item):

    for i in arr:

        if i == item:

            return i

    return False

bash

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

Следующая функция содержит два блока кода, которые выполняются последовательно — в таком случае сложность складывается:

def new_function(arr):

    for i in arr:

        print(i)  

    for i in arr:

        for j in arr:

            print(i * j)

Первый цикл обходит все элементы массива с количеством элементов n, значит, сложность линейная. Второй блок представляет из себя внешний и вложенный цикл, каждый из которых тоже выполняет полный обход массива — сложность равна O(n2). Теперь нужно сложить эти два результата: O(n + n2). По правилу учитывается слагаемое, которое растет быстрее, значит, итоговая сложность равна O(n2).

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

Практические примеры алгоритмов с разной сложностью

Бинарный поиск и его эффективность по сравнению с линейным

Бинарный поиск позволяет находить элементы гораздо быстрее линейного, и с увеличением количества элементов в массиве, разрыв в скорости растет. Так, если на вход программе передан массив из 15 элементов, для выполнения линейного поиска (O(n)) понадобится до 15 операций, а для бинарного (O(log n)) — около 4. Если же массив состоит из миллиона элементов, то для линейного поиска потребуется до миллиона операций, а для бинарного — около 20.

Сложность операций в структурах данных

Рассмотрим сложность основных операций в нескольких структурах данных:

массив — это оптимальная структура, если задача предполагает наличие возможности быстрого доступа к элементам по индексу: в таком случае сложность составляет O(1). Однако для всех операций, требующих перебора значений, сложность линейна;
хеш-таблицы позволяют эффективно выполнять поиск, вставку и удаление элементов по ключам со сложностью O(1), но в худшем случае она может стать линейной — O(n). Соответственно, хеш-таблицы применимы в тех случаях, когда нужно обеспечить быстрый доступ к данным;
в бинарном дереве поиска операции вставки, удаления и поиска выполняются с линейной сложностью, а если дерево сбалансировано, например, это AVL-дерево, — с логарифмической. Бинарное дерево поиска также сохраняет упорядоченность данных;
в связных списках выполнение вставки и удаления элементов в начале происходит с константной сложностью, но поиск и доступ по индексу предполагают перебор всех узлов, поэтому сложность линейна;
в стеке сложность операций вставки и удаления элементов константная. Но так как в основе классических реализаций стека лежит принцип LIFO (last in — first out), доступ возможен только к элементу на вершине, а доступ к произвольным элементам ограничен.

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

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

приложения для анализа Big Data;
приложения, обрабатывающие данные в режиме реального времени;
веб-приложения и социальные сети, обрабатывающие/реагирующие на запросы пользователей.

Часто задаваемые вопросы по сложности алгоритмов

Как понять, что алгоритм имеет сложность O(log n)?

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

Если исходный массив содержит 32768 элементов, то поиск завершится максимум за 15 итераций (log 32768 = 15).

Почему сложность алгоритмов так важна в программировании?

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

Как выбрать структуру данных, оптимальную по сложности?

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

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

Заключение: значимость сложности алгоритмов в программировании

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

Чтобы добиться желаемой производительности, стоит оптимизировать ее, анализировать задачу, которую нужно решить, и подбирать для ее решения подходящую структуру данных.

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

Также можно выделить случаи, когда эффективность приоритетна:

работа с большими объемами данных;
обработка данных в режиме реального времени;
системы, где важна масштабируемость.

Есть и обратные ситуации, когда эффективность второстепенна:

работа с небольшими объемами данных;

учебные задачи, требующие быстрого решения, а не оптимального по производительности;
отсутствие сложных вычислений в приложении.