О чем Big O?
Привет, сегодня я буду писать обо всей шумихе вокруг нотации Big O.
Если вы немного разбираетесь в мире программирования, вы, вероятно, слышали о нотации Big O. И вы, вероятно, спрашивали себя, что такое Big O? Какова цель Big O вообще!?
Ну, я намерен ответить на эти вопросы здесь и даже больше.
Давайте начнем с того, что зададим первый вопрос: что, черт возьми, за нотация большого O?
Что ж, нотация Big O — это нотация, которая инкапсулирует математическую функцию для измерения производительности алгоритма в худшем случае. Большой О предназначен для измерения того, НАСКОЛЬКО ХОРОШО алгоритм будет работать на входе, приближающемся к бесконечности.
Обратите внимание, что я написал НАСКОЛЬКО ХОРОШО вместо СКОЛЬКО ВРЕМЕНИ алгоритму потребуется выполнить конкретную задачу при определенных входных данных. Почему? Потому что, чтобы измерить, сколько времени алгоритму потребуется для выполнения определенной задачи, нам потребуется много информации, которую может быть даже невозможно собрать, например: место ввода, мощность ЦП, архитектура ЦП, вычислительная мощность, доступная в момент выполнения. алгоритм, язык, который выполняет алгоритм, компилятор и так далее…
Поэтому, когда ученые-компьютерщики сошли с ума, столкнувшись с проблемой множества переменных для вычисления, и они начали понимать, что было бы невозможно разделить эффективность алгоритма с учетом этих переменных, они придумали концепцию асимптотической записи. . Асимптотическая запись означает язык, который позволяет нам анализировать время работы алгоритма при входных данных, приближающихся к бесконечности.
Проще говоря, нотация Big O — это способ измерить, насколько хорошо алгоритм будет работать при входных данных, приближающихся к бесконечности.
Какова цель Большого О?
Предположим, вы и ваш друг, тоже программист, соревнуетесь, кто создаст алгоритм, решающий ту же задачу быстрее. Как бы вы это сделали? Если алгоритм решает задачу поиска и входной массив упорядочен, вы можете подсчитать, какой алгоритм сделает меньше предположений, чем другой. Но как насчет времени? Сколько времени потребуется для выполнения моего алгоритма? а что, если алгоритм даже не проблема поиска?
Как мы можем игнорировать все те переменные, которые зависят локально, и знать, насколько хорошо наш алгоритм будет работать на любом компьютере в мире? Было бы несправедливо подсчитывать, сколько времени работает алгоритм на персональном компьютере моего друга, который может быть быстрее моего, верно? Да, ты прав.
Итак, ученые-компьютерщики сидели и думали об этом, и они пришли с нотацией, цель которой состоит в том, чтобы измерить, насколько хорошо алгоритм будет работать на любом данном языке и на любом компьютере в мире: нотация Big O.
Наша первая нотация: постоянное время
Теперь, когда мы знаем, что такое нотация Big O и какова ее цель, мы собираемся изучить, как измерять и выражать в терминах нотации Big O.
Для выполнения задачи компьютеру требуется время. Это интуитивно понятно.
Мы говорим, что компьютеру требуется большое O постоянного времени, если время, необходимое алгоритму для завершения работы при независимом размере входных данных, постоянно.
Для формального выражения мы используем букву O, за которой следует закрывающая скобка () плюс математическая функция внутри скобки, в другими терминами, чтобы выразить постоянное время, мы бы написали: O(1), почему 1? а не 2? 3? 4? Потому что один был выбран для представления постоянного времени.
Обозначение N
Что произойдет, если у вас есть алгоритм, который принимает на вход массив размера N и выполняет постоянное время вычислений в каждом элементе массива? В терминах нотации Big O мы бы сказали, что для завершения алгоритма потребуется O (N).
Что это значит? Это означает, что для любого заданного массива размера N потребуется (N * постоянное) время вычислений, чтобы завершить алгоритм.
Обозначение N²
Иногда нам приходится выполнять N вычислений для каждого элемента N входного размера. Это тот случай, когда у вас есть два форса, вложенных друг в друга.
Например:
for item1 in array: for item2 in array: do(something, with, item1, and, item2)
Это дало бы нам O(N²)!
Теперь, если у вас есть базовое представление о математических функциях, вы интуитивно поймете, что N ‹ N². Поэтому мы можем сделать вывод, что время работы O(N) МЕНЬШЕ, чем O(N²).
Другие обозначения
До сих пор мы видели три обозначения, но есть и другие.
Вот некоторые из них: √N ,log N, n log n, N², N³, N!(факториал), 2^N и так далее…
Как рассчитать Big O алгоритма
Первый шаг для вычисления большого O алгоритма — вычислить, сколько вычислений алгоритму потребуется для завершения.
Мы можем начать с простого алгоритма, который возвращает первый элемент входного массива:
def display_first_element(input):
return input[0]Неважно, каков размер входных данных, объем работы, который должен будет выполнить алгоритм, — это просто найти первый элемент (постоянное время для массивов) и вернуть его. Мы бы сказали, что этому алгоритму требуется время O(1 + 1) для выполнения своей задачи. Почему? Потому что, если мы собираемся быть строгими, нам нужно будет рассчитать количество времени, затраченное на поиск массива (постоянное время O (1)) плюс количество времени для возврата результата, который также оказывается O (1) . Поэтому, если мы суммируем их оба, мы получим O (1 + 1).
Суммирующие константы
Вернемся к предыдущему примеру, где мы берем входной массив и возвращаем первый элемент массива. Он говорит, что его время работы O (1 + 1). Другими словами, это сумма времени выполнения получения первого элемента (который является постоянным) и суммы возврата элемента. Обе операции выполняются за O(1), и, как я уже говорил ранее, O(1) — это постоянное время работы. Но сколько времени? Дело в том, что мы не знаем, потому что не знаем тех переменных, которые невозможно вычислить. Это может быть 1 мс 10 мс 1 сек, мы не знаем. Мы знаем, что это постоянное время. Размер массива не имеет значения, для завершения потребуется ПОСТОЯННОЕ время.
Следовательно, для Big O нет разницы между выражением суммы Big(1 + 1) и Big(1), потому что сумма двух постоянных времени дает само постоянное время.
Из-за этого мы суммируем постоянное время и представляем с помощью обозначения постоянного времени, которое равно O (1).
Удаление констант
Теперь давайте предположим, что у нас есть алгоритм O(N), то есть он будет проходить через все элементы массива в худшем случае.
Следующий алгоритм принимает массив и цель в качестве входных данных, пытается найти цель в массиве и, наконец, возвращает индекс элемента в массиве:
def n_algorithm(input, target):
index = 0
for item in input:
if item == target:
return index
index += 1
return NoneЕсли бы мы были строгими, мы бы начали вычислять время работы индекса = 0, которое является постоянным временем O (1), затем мы перешли бы к циклу, который занял бы O (3 * N), почему? Потому что есть три операции, которые выполняются путем итерации N: 1) получение значения из ввода, 2) сравнение с целью и, наконец, 3) увеличение индекса. Все они требуют постоянного времени для вычисления, но они выполняются N раз. Таким образом, у нас есть O (3 * N) время работы. И, наконец, у нас есть возвращаемый оператор, который либо выполняется внутри цикла, либо вне цикла один раз = O (1). Следовательно, у нас есть O (1 + 1 + 3 * N).
Вот факт, Big O не заботится о константах. Он заботится только о скорости роста функции. Тогда для нотации Big O O (3 * N) совпадает с O (N).
Зная, что у нас есть O (1 + N), что равно O (N), объяснение этого приходит в следующем разделе, который…
Отбрасывание недоминирующих терминов
Предположим, у нас есть алгоритм, который выполняет линейный поиск, а затем выполняет вычисление O(N²). Следующее:
def f(array): for item in array: do(something)for item1 in array: for item2 in array: do(something, with, item1, and, item2)
Какова будет временная сложность этого алгоритма? НА)? O(N²) или O(N + N²)? Если вы сказали O(N²), то вы чертовски правы. Почему? Потому что, когда мы вычисляем большое О, мы отбрасываем недоминирующие термины. Что это значит? Это означает, что мы рассматриваем только те члены, которые преобладают над скоростью роста. Независимо от того, насколько велико N, N² всегда будет, я имею в виду, ВСЕГДА будет значительно больше, чем N. В свете этого мы рассматриваем только доминирующие термины, в нашем случае N².
Заключение
Нотация Big O — довольно мощная и полезная нотация. Это позволяет нам объективно анализировать время работы алгоритма на любом компьютере в мире, на любом заданном языке с любым компилятором.
Это позволяет нам сравнивать алгоритмы и решать, какой из них будет работать быстрее.
Это все на данный момент.
Надеюсь, вам понравилось.
Спасибо за прочтение.
Тебе понравилось? Вот еще сила для вас:
