Давайте посмотрим на нотацию BigO с другой точки зрения.

Я искренне верю, что нет ничего, чему нельзя было бы научиться, если начать с самых основ.

Если вы объедините правильные ресурсы и желание учиться, ничто не сможет устоять перед вами и вашими мечтами.

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

Начнем с определения:

Обозначение «большое О» — это математическое обозначение, описывающее предельное поведение функции, когда аргумент стремится к определенному значению или бесконечности.

Как мы это понимаем?

В информатике почти всегда есть несколько способов решения проблемы. Наша работа как инженеров-программистов заключается в том, чтобы найти наиболее эффективное решение и внедрить его. Но что значит эффективно? Это самый быстрый способ? Это тот, который занимает меньше места, чем другие? На самом деле, это зависит. Это связано исключительно с вашей конкретной проблемой. Если вы работаете во встроенных системах с ограниченной памятью, например, если проблема состоит в том, чтобы рассчитать требуемую мощность в ваттах для разморозки 200 г мяса в микроволновой печи, вы можете обменять алгоритм, который более эффективно использует память и занимает 1 с, чтобы сделать это вычисление на другое, которое выполняет это вычисление в миллисекундах, но требует гораздо больше памяти. Ведь даже если запуск занимает миллисекунды, сам процесс разморозки потребует от 10 до 15 минут.

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

В общем, программная инженерия — это компромиссы. Хороший инженер-программист должен знать требования и предлагать решения для их выполнения.

Учитывая все вышесказанное, сейчас понятно, что нам нужно каким-то образом количественно оценить и измерить влияние любого алгоритма на производительность и память. Один из способов сделать это — посмотреть, сколько секунд требуется для завершения одного алгоритма. Это может дать некоторую ценность, но проблема в том, что если мой алгоритм поиска занимает от 2 до 3 секунд на моем ноутбуке с массивом из 1000 элементов, он может занять меньше времени, чем на другом более мощном ноутбуке, верно? Даже если мы согласимся взять производительность моего ноутбука за основу, мы не в курсе, что произойдет, когда размер массива удвоится? Что происходит, когда размер массива достигает бесконечности?

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

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

Если вы скопируете массив из 10 элементов в другой массив, вам нужно будет выполнить цикл по всему массиву, что означает 10 операций. Что в нотации BigO выражается как O(N), где N — размер входного массива. Сложность пространства для этого примера снова равна O(N), потому что вы собираетесь выделить больше памяти для скопированного массива.

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

[1, 2, 3, 4, 5]  # you will perform 5 operations here to find it

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

[5, 1, 2, 3, 4]  # you will perform only one operation in this case

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

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

O(1) Постоянное время

Понятно, что это лучшая нотация BigO, которую может иметь алгоритм. Когда вы хотите выполнить определенное действие и можете выполнить его только за одну операцию. Давайте посмотрим на пример с использованием python:

country_phone_code_map = {
    'Albania': '+355',
    'Algeria': '+213',
    'American Samoa': '+684',
}
country = 'Albania'
print(country_phone_code_map[country])  # 1 operation
>>> '+355'

В python, если вы хотите выполнить поиск элемента в dict, тогда операция будет иметь временную сложность O (1). Dict в Python похож на HashMap в других языках.

Точнее, наихудший сценарий — O(N), и это связано с тем, насколько хорошо реализована структура данных. Ключевую роль здесь играет хэш-функция, но в целом принято считать, что BigO для поиска в dict составляет O (1). Если вы находитесь на собеседовании по программированию, вы можете предположить, что это O (1).

Хочу остановиться на еще одной очень важной теме при расчете BigO. Константы. Вы можете знать или не знать, что константы игнорируются при вычислении BigO. Я не хочу, чтобы вы просто принимали это как правило и не задумывались о причинах этого.

Именно поэтому я визуализирую нотацию BigO. Итак, давайте предположим, что для приведенного выше примера нам также потребуется получить 3-х и 2-буквенный код страны, имея название страны. Это означает, что у нас есть какое-то другое сопоставление для 2- и 3-буквенного кода страны, и нам просто нужно выполнить еще 2 операции внутри той же функции.

country_phone_code_map = {
    'Albania': '+355',
    'Algeria': '+213',
}
country_2_letter_code_map = {
    'Albania': 'AL',
    'Algeria': 'DZ',
}
country_3_letter_code_map = {
    'Albania': 'ALB',
    'Algeria': 'DZA',
}
country = 'Albania'

phone_code = country_phone_code_map[country]  # 1 operation
two_letter_code = country_2_letter_code_map[country]  # 1 operation
three_letter_code = country_3_letter_code_map[country]  # 1 operation

Если мы продолжим считать количество операций, как мы договаривались делать раньше. Здесь у нас будет 3 операции, которые сделают BigO = O(3), верно?

Давайте визуализируем это:

Как видите, количество операций увеличилось на 3. Это означает, что мы фактически выполняем более одной операции для выполнения этой задачи. Но BigO говорит, что если есть константы, просто игнорируйте их. Таким образом, O(3) или O(2n) или O(2n + 1) будут соответственно O(1), O(n), O(n).

Это потому, что нас интересует предел функции, когда N стремится к бесконечности, а не то, сколько именно операций она будет выполнять. Мы не вычисляем количество операций, а вместо этого нам интересно посмотреть, как количество операций будет расти по мере того, как N стремится к бесконечности. Вы можете подумать, что да, но алгоритм с O(1000n) медленнее, чем с O(n), поэтому нам нужно учитывать, что 1000 мы не можем его игнорировать. Это правда, но это число 1000 является константой, и оно не становится больше, чем N. Даже когда N равно 10, оно останется 1000, даже когда N равно 1B, оно останется 1000. Таким образом, оно не дает нам никакой ценной информации относительно пределы функции. Единственная важная часть — O(n), которая говорит нам о том, что чем больше вы увеличиваете, тем больше операций вы собираетесь выполнять для выполнения задачи.

O(logn) Логарифмическое время

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

Здесь важно то, что когда мы говорим о логарифме в информатике без указания основания, мы всегда говорим о логарифме с основанием 2.В математике мы привыкли к логарифму. с основанием 10 в этом случае, но в информатике все по-другому. Просто имейте это в виду, когда имеете дело с анализом сложности.

Как вы можете видеть на изображении выше, это на самом деле очень хорошая временная сложность. Иметь сложность O(logn) на простом английском языке означает, что каждый раз, когда размер входных данных удваивается, нам нужно всего лишь сделать еще одну итерацию, чтобы выполнить задачу. Когда N около миллиона, нам нужно выполнить только 20 операций, а когда оно достигает 1 миллиарда, нам нужно выполнить только 30 операций. Вы можете увидеть мощь алгоритма с временной сложностью O(logn). Для такого огромного увеличения N нам нужно выполнить еще 10 операций.

O(N) линейное время

В этом случае, когда N стремится к бесконечности, количество операций также стремится к бесконечности с той же скоростью, что и N. Примером является линейный поиск, который мы обсуждали ранее.

array = [1, 2, 3, 4, 5]
number = 5
for index, item in enumerate(array):  # loop n times
    if item == number:  # check for equality
        print(f'Found item at {index=}')
        break
        
>>> Found item at index=4

O(NlogN) Лог-линейное время

Эта нотация обычно используется вместе с алгоритмами сортировки. Взгляните на эту визуализацию для сортировки слиянием. Сортировка слиянием делит массив на две половины O(logn) и требует линейного времени O(n) для объединения разделенных массивов.

O(N²) квадратичное время

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

def bubble_sort(data):
    for _ in range(len(data)):  # O(n)
        for i in range(len(data) - 1):  # nested O(n)

            if data[i] > data[i + 1]:
                data[i], data[i + 1] = data[i + 1], data[i]
    return data

Поскольку второй цикл является вложенным, мы умножим его сложность на сложность первого цикла. Что равно O(n) * O(n) = O(n²)

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

O(N³) кубическое время

Простейшим примером может быть алгоритм с 3 вложенными циклами for.

for i in range(len(array)):  # O(n)
    for j in range(len(array)):  # O(n)
        for p in range(len(array)):  # O(n)
            print(i, j, p)

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

O(2^N) Экспоненциальное время

Самый известный пример этой записи — нахождение n-го числа Фибоначчи с помощью рекурсивного решения.

def nth_fibonacci(n: int) -> int:
    if n in [1, 2]:
        return 1

    return nth_fibonacci(n - 1) + nth_fibonacci(n - 2)

O(N!) Факторное время

Примером этого может быть создание всех перестановок списка. Взгляните на Задачу коммивояжера.

Возьмите самый важный фактор

Мы уже говорили об исключении констант при вычислении сложности алгоритма, поскольку они не представляют для нас никакой ценности. Есть еще кое-что относительно этого правила. При выполнении анализа сложности мы можем получить алгоритм, который выполняет более 1 типа операций с заданными входными данными. Например, нам может понадобиться некоторая функция для первоначальной сортировки массива, а затем поиска в нем. Предположим, что это будет одна операция сортировки со сложностью O(NlogN) плюс еще одна операция поиска со сложностью O(logN).

Временная сложность такой функции будет O(NlogN) + O(logN). Давайте визуализируем это:

Если вы посмотрите на этот график, вы заметите, что влияние O(NlogN) больше, чем влияние O(logN), поскольку график больше похож на график O(NlogN) по сравнению с O(logN) . Мы можем даже математически показать это, сделав это.

O(NlogN) + O(logN) = O((N+1)logN)  # factorize
O((N+1)logN) = O(NlogN)  # drop constant 1

В этом случае они относительно близки друг к другу, и разница не очевидна, но если мы возьмем другой пример, такой как O(N! + N³ + N² + N), мы заметим, что влияние обозначений, кроме N! так мало по сравнению с N! когда N становится слишком большим!

Мы можем легко вычислить 1 000 000 ^ 3, но попробуем сделать то же самое для факториала 1 000 000.

Факториал 10 равен 3 628 800, а 10³ — всего 1000. Как видите, влияние N³ настолько мало по сравнению с N! что мы можем на самом деле игнорировать его. Вот почему, когда мы суммируем несколько обозначений, мы берем самый важный фактор.

Что очень важно знать при выборе наиболее важного фактора, так это то, что мы группируем факторы по входным данным. Это означает, что если у нас есть алгоритм, который работает с двумя разными массивами, один из которых имеет размер N, а другой — размер M, а сложность алгоритма равна O(N² + N + M³ + M²), то мы не можем просто сказать, что наибольший фактор равен M³. поэтому сложность равна O(M³). Это неверно, потому что это совершенно отдельные переменные в нашей функции. Наш алгоритм зависит от того, работают ли они оба, поэтому правильно будет убрать самые высокие коэффициенты для обеих переменных. Мы исключаем N, так как N² больше, и мы исключаем M², так как M³ больше, и результат равен O(N² + M³).

Заключение

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

Рекомендации