Big O Analysis — это метод анализа и ранжирования эффективности алгоритмов.
Это позволяет выбрать наиболее эффективные и масштабируемые алгоритмы. Эта статья представляет собой шпаргалку Big O, объясняющую все, что вам нужно знать о нотации Big O.
Оглавление
Что такое анализ Big O?
Big O Analysis — это метод анализа того, насколько хорошо масштабируются алгоритмы. В частности, мы спрашиваем, насколько эффективен алгоритм при увеличении размера входных данных.
Эффективность — это то, насколько хорошо используются системные ресурсы при производстве результатов. Ресурсы, которые нас интересуют в первую очередь, — это время и память.
Поэтому при выполнении анализа Big O мы задаем следующие вопросы:
Ответом на первый вопрос является пространственная сложность алгоритма, а ответом на второй — его временная сложность. Мы используем специальную нотацию под названием Big O Notation, чтобы выразить ответы на оба вопроса. Далее об этом будет рассказано в шпаргалке Big O.
Предварительные условия
Прежде чем двигаться дальше, я должен сказать, что для того, чтобы максимально эффективно использовать эту шпаргалку Big O, вам нужно немного понимать алгебру. Кроме того, поскольку я буду приводить примеры Python, полезно немного разобраться в Python. Глубокое понимание не требуется, поскольку вы не будете писать код.
Как выполнить анализ Big O
В этом разделе мы расскажем, как выполнить анализ Big O.
При выполнении анализа сложности Big O важно помнить, что производительность алгоритма зависит от того, как структурированы входные данные.
Например, алгоритмы сортировки работают быстрее всего, когда данные в списке уже отсортированы в правильном порядке. Это лучший сценарий для производительности алгоритма. С другой стороны, те же алгоритмы сортировки работают медленнее всего, когда данные структурированы в обратном порядке. Это худший сценарий.
При выполнении анализа Big O мы рассматриваем только наихудший сценарий.
Анализ космической сложности
Давайте начнем эту шпаргалку Big O с описания того, как выполнить анализ пространственной сложности. Мы хотим рассмотреть, как дополнительная память, которую использует алгоритм, масштабируется по мере того, как входные данные становятся все больше и больше.
Например, функция ниже использует рекурсию для цикла от n до нуля. Его пространственная сложность прямо пропорциональна n. Это связано с тем, что с ростом n увеличивается и количество вызовов функций в стеке вызовов. Итак, его пространственная сложность равна O(n).
def loop_recursively(n):
if n == -1:
return
else:
print(n)
loop_recursively(n - 1)
Однако лучшая реализация будет выглядеть так:
def loop_normally(n):
count = n
while count >= 0:
print(count)
count =- 1
В приведенном выше алгоритме мы создаем только одну дополнительную переменную и используем ее для цикла. Если бы n становилось все больше и больше, мы все равно использовали бы только одну дополнительную переменную. Следовательно, алгоритм имеет постоянную пространственную сложность, обозначаемую символом «O(1)».
Сравнивая пространственную сложность двух приведенных выше алгоритмов, мы пришли к выводу, что цикл while более эффективен, чем рекурсия. Это основная цель анализа Big O: анализ того, как изменяются алгоритмы, когда мы запускаем их с более крупными входными данными.
Анализ временной сложности
При выполнении анализа временной сложности нас не беспокоит рост общего времени, затрачиваемого алгоритмом. Скорее, нас беспокоит рост количества выполняемых вычислительных шагов. Это связано с тем, что фактическое время зависит от многих системных и случайных факторов, которые трудно учесть. Итак, мы лишь отслеживаем рост вычислительных шагов и предполагаем, что каждый шаг равен.
Чтобы продемонстрировать анализ временной сложности, рассмотрим следующий пример:
Предположим, у нас есть список пользователей, в котором у каждого пользователя есть идентификатор и имя. Наша задача — реализовать функцию, которая возвращает имя пользователя при присвоении ему идентификатора. Вот как мы могли бы это сделать:
users = [
{'id': 0, 'name': 'Alice'},
{'id': 1, 'name': 'Bob'},
{'id': 2, 'name': 'Charlie'},
]
def get_username(id, users):
for user in users:
if user['id'] == id:
return user['name']
return 'User not found'
get_username(1, users)
Учитывая список пользователей, наш алгоритм просматривает весь массив пользователей, чтобы найти пользователя с правильным идентификатором. Когда у нас 3 пользователя, алгоритм выполняет 3 итерации. Когда у нас 10, он выполняет 10.
Следовательно, количество шагов линейно и прямо пропорционально количеству пользователей. Итак, наш алгоритм имеет линейную временную сложность. Однако мы можем улучшить наш алгоритм.
Предположим, что вместо хранения пользователей в списке мы сохранили их в словаре. Тогда наш алгоритм поиска пользователя будет выглядеть так:
users = {
'0': 'Alice',
'1': 'Bob',
'2': 'Charlie'
}
def get_username(id, users):
if id in users:
return users[id]
else:
return 'User not found'
get_username(1, users)
Предположим, что с помощью этого нового алгоритма в нашем словаре было 3 пользователя; мы выполним несколько шагов, чтобы получить имя пользователя. Предположим, у нас было больше пользователей, скажем, десять. Чтобы получить пользователя, мы выполнили бы то же количество шагов, что и раньше. По мере роста количества пользователей количество шагов для получения имени пользователя остается постоянным.
Следовательно, этот новый алгоритм имеет постоянную сложность. Не имеет значения, сколько у нас пользователей; количество выполняемых вычислительных шагов одинаково.
Что такое нотация Big O?
В предыдущем разделе мы обсудили, как вычислить пространственную и временную сложность Big O для различных алгоритмов. Для описания сложностей мы использовали такие слова, как линейный и постоянный. Другой способ описания сложностей — использовать нотацию Big O.
Обозначение Big O — это способ представления пространственной или временной сложности алгоритма. Обозначения относительно просты; это буква О, за которой следуют круглые скобки. В круглых скобках мы пишем функцию от n, представляющую конкретную сложность.
Линейная сложность обозначается буквой n, поэтому мы будем писать ее как O(n) (читается как «O из n»). Постоянная сложность обозначается цифрой 1, поэтому мы будем писать ее как O(1).
Есть и более сложные моменты, о которых мы поговорим в следующем разделе. Но обычно, чтобы описать сложность алгоритма, выполните следующие шаги:
Результатом этого становится термин, который мы используем в скобках.
Пример:
Рассмотрим следующую функцию Python:
users = [
'Alice',
'Bob',
'Charlie'
]
def print_users(users):
number_of_users = len(users)
print("Total number of users:", number_of_users)
for i in number_of_users:
print(i, end=': ')
print(user)
Теперь мы рассчитаем сложность алгоритма Big O Time.
Сначала мы напишем математическую функцию nf(n), чтобы представить количество вычислительных шагов, выполняемых алгоритмом. Напомним, что n представляет размер ввода.
В нашем коде функция выполняет два шага: один для расчета количества пользователей, а другой для вывода количества пользователей. Затем для каждого пользователя он выполняет два шага: один — для печати индекса, другой — для печати пользователя.
Следовательно, функцию, которая лучше всего представляет количество предпринятых вычислительных шагов, можно записать как f(n) = 2 + 2n. Где n — количество пользователей.
Переходя ко второму шагу, мы выбираем наиболее доминирующий термин. 2n — линейный член, а 2 — постоянный член. Линейный является более доминирующим, чем постоянный, поэтому мы выбираем 2n, линейный член.
Итак, наша функция теперь f(n) = 2n.
Последний шаг – исключить коэффициенты. В нашей функции у нас есть коэффициент 2. Поэтому мы устраняем это. И функция становится f(n) = n. Это термин, который мы используем в скобках.
Следовательно, временная сложность нашего алгоритма равна O(n) или линейной сложности.
Различные сложности Big O
В последнем разделе нашей шпаргалки Big O показаны различные сложности и соответствующие графики.
№1. Постоянный
Постоянная сложность означает, что алгоритм использует постоянный объем пространства (при выполнении анализа пространственной сложности) или постоянное количество шагов (при выполнении анализа временной сложности). Это наиболее оптимальная сложность, поскольку алгоритму не требуется дополнительное пространство или время по мере роста входных данных. Таким образом, он очень масштабируем.
Постоянная сложность представлена как O(1). Однако не всегда возможно написать алгоритмы, работающие с постоянной сложностью.
№2. логарифмический
Логарифмическая сложность представлена термином O(log n). Важно отметить, что если в информатике не указано основание логарифма, мы предполагаем, что оно равно 2.
Следовательно, log n равен log2n. Известно, что логарифмические функции сначала растут быстро, а затем замедляются. Это означает, что они масштабируются и эффективно работают со все большим числом n.
№3. Линейный
Для линейных функций, если независимая переменная масштабируется в p раз. Зависимая переменная масштабируется с тем же коэффициентом p.
Следовательно, функция с линейной сложностью растет в тот же раз, что и входной размер. Если размер входных данных увеличится вдвое, увеличится и количество вычислительных шагов или использование памяти. Линейная сложность обозначается символом O(n).
№4. линейный
O (n * log n) представляет линейные функции. Линейные функции — это линейная функция, умноженная на функцию логарифма. Следовательно, линеарифмическая функция дает результаты немного большие, чем линейные функции, когда log n больше 1. Это связано с тем, что n увеличивается при умножении на число, большее 1.
Log n больше 1 для всех значений n больше 2 (помните, что log n равен log2n). Следовательно, для любого значения n больше 2 линейные функции менее масштабируемы, чем линейные функции. Из которых в большинстве случаев n больше 2. Таким образом, линейные функции обычно менее масштабируемы, чем логарифмические функции.
№5. квадратичный
Квадратичная сложность представлена O(n2). Это означает, что если размер ввода увеличится в 10 раз, количество предпринятых шагов или использованного пространства увеличится в 102 раза или 100! Это не очень масштабируемо, и, как видно из графика, сложность очень быстро возрастает.
Квадратичная сложность возникает в алгоритмах, в которых вы выполняете цикл n раз, а для каждой итерации вы повторяете цикл n раз, например, в пузырьковой сортировке. Хотя в целом это не идеально, иногда у вас нет другого выбора, кроме как реализовать алгоритмы с квадратичной сложностью.
№6. Полиномиальный
Алгоритм с полиномиальной сложностью обозначается как O(np), где p — некоторое постоянное целое число. P представляет порядок повышения n.
Эта сложность возникает, когда у вас есть определенное количество вложенных циклов. Разница между полиномиальной сложностью и квадратичной сложностью заключается в том, что квадратичная сложность имеет порядок 2, тогда как полином имеет любое число больше 2.
№7. Экспоненциальный
Экспоненциальная сложность растет даже быстрее, чем полиномиальная. В математике значением по умолчанию для экспоненциальной функции является константа e (число Эйлера). Однако в информатике значение по умолчанию для экспоненциальной функции равно 2.
Экспоненциальная сложность обозначается символом O(2n). Когда n равно 0, 2n равно 1. Но когда n увеличивается до 5, 2n увеличивается до 32. Увеличение n на единицу удвоит предыдущее число. Следовательно, экспоненциальные функции не очень масштабируемы.
№8. Факториал
Факториальная сложность обозначается символом O(n!). Эта функция также очень быстро растет и поэтому не масштабируется.
Заключение
В этой статье мы рассмотрели анализ Big O и способы его расчета. Мы также обсудили различные сложности и обсудили их масштабируемость.
Далее вы можете попрактиковаться в анализе Big O в алгоритме сортировки Python.