Нотация Big O и анализ алгоритмов с примерами Python
Существует несколько способов решения проблемы с помощью компьютерной программы. Например, существует несколько способов сортировки элементов в массиве. Вы можете использовать сортировку слиянием , сортировку пузырьками , сортировку вставкой и т. Д. Все эти алгоритмы имеют свои плюсы и минусы. Алгоритм можно рассматривать как процедуру или формулу для решения конкретной задачи. Вопрос в том, какой алгоритм использовать для решения конкретной задачи, когда существует несколько решений этой проблемы?
Анализ алгоритмов относится к анализу сложности различных алгоритмов и поиску наиболее эффективного алгоритма для решения поставленной задачи. Big-O Notation – это статистическая мера, используемая для описания сложности алгоритма.
В этой статье мы кратко рассмотрим анализ алгоритмов и нотацию Big-O. Мы увидим, как нотация Big-O может быть использована для определения сложности алгоритма с помощью различных функций Python.
Почему важен Анализ Алгоритмов?
Чтобы понять, почему важен анализ алгоритмов, воспользуемся простым примером.
Предположим, менеджер дает задание двум своим сотрудникам разработать алгоритм на языке Python, который вычисляет факториал числа, введенного пользователем.
Алгоритм, разработанный первым сотрудником, выглядит так:
def fact(n):
product = 1
for i in range(n):
product = product * (i+1)
return product
print (fact(5))
Обратите внимание, что алгоритм просто принимает целое число в качестве аргумента. Внутри функции fact переменная с именем product инициализируется значением 1. Цикл выполняется от 1 до N, и во время каждой итерации значение в product умножается на число, повторяемое циклом, и результат снова сохраняется в переменной product . После выполнения цикла переменная product будет содержать факториал.
Аналогично, второй сотрудник также разработал алгоритм, который вычисляет факториал числа. Второй сотрудник использовал рекурсивную функцию для вычисления факториала программы, как показано ниже:
def fact2(n):
if n == 0:
return 1
else:
return n * fact2(n-1)
print (fact2(5))
Менеджер должен решить, какой алгоритм использовать. Для этого он должен найти сложность алгоритма. Один из способов сделать это-найти время, необходимое для выполнения алгоритмов.
В записной книжке Jupyter вы можете использовать литерал %time it , за которым следует вызов функции, чтобы найти время, затраченное функцией на выполнение. Посмотрите на следующий сценарий:
%timeit fact(50)
Выход:
9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Вывод говорит, что алгоритм занимает 9 микросекунд (плюс/минус 45 наносекунд) на цикл.
Аналогично выполните следующий сценарий:
%timeit fact2(50)
Выход:
15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Второй алгоритм, включающий рекурсию, занимает 15 микросекунд (плюс/минус 427 наносекунд).
Время выполнения показывает, что первый алгоритм работает быстрее по сравнению со вторым алгоритмом, включающим рекурсию. Этот пример показывает важность алгоритмического анализа. В случае больших входных данных разница в производительности может стать более значительной.
Однако время выполнения не является хорошей метрикой для измерения сложности алгоритма, поскольку оно зависит от аппаратного обеспечения. Необходим более объективный анализ метрик сложности алгоритмов. Вот тут-то и вступает в игру нотация Big O.
Анализ алгоритмов с нотацией Big-O
Нотация Big-O-это метрика, используемая для определения сложности алгоритма. В принципе, обозначение Big-O означает связь между входными данными алгоритма и шагами, необходимыми для выполнения алгоритма. Он обозначается большой буквой “О”, за которой следуют открывающая и закрывающая скобки. Внутри круглой скобки связь между входными данными и шагами, выполняемыми алгоритмом, представлена с помощью буквы “n”.
Например, если существует линейная зависимость между входными данными и шагом, выполняемым алгоритмом для завершения его выполнения, то используемая нотация Big-O будет O(n). Аналогично, обозначение Big-O для квадратичных функций равно O(n^2)
Ниже приведены некоторые из наиболее распространенных функций Big-O:
| Постоянный | O(c) |
| Линейный | O(n) |
| Квадратный | O(n^2) |
| Кубический | O(n^3) |
| Экспонентный | O(2^n) |
| Логарифмический | O(log(n)) |
| Логарифмический линейный | O(nlog(n)) |
Чтобы получить представление о том, как вычисляется нотация Big-O, давайте рассмотрим некоторые примеры постоянной, линейной и квадратичной сложности.
Постоянная сложность (O(C))
Сложность алгоритма называется постоянной, если шаги, необходимые для завершения выполнения алгоритма, остаются постоянными, независимо от количества входных данных. Постоянная сложность обозначается через O(c), где c может быть любым постоянным числом.
Давайте напишем простой алгоритм на Python, который находит квадрат первого элемента в списке и затем выводит его на экран.
def constant_algo(items):
result = items[0] * items[0]
print ()
constant_algo([4, 5, 6, 8])
В приведенном выше скрипте, независимо от размера ввода или количества элементов во входном списке элементов , алгоритм выполняет только 2 шага: находит квадрат первого элемента и выводит результат на экран. Следовательно, сложность остается постоянной.
Если вы нарисуете линейный график с переменным размером входных данных items на оси x и количеством шагов на оси y, вы получите прямую линию. Чтобы визуализировать это, выполните следующий сценарий:
import matplotlib.pyplot as plt
import numpy as np
x = [2, 4, 6, 8, 10, 12]
y = [2, 2, 2, 2, 2, 2]
plt.plot(x, y, 'b')
plt.xlabel('Inputs')
plt.ylabel('Steps')
plt.title('Constant Complexity')
plt.show()
Выход:
Линейная сложность (O(n))
Сложность алгоритма называется линейной, если шаги, необходимые для завершения выполнения алгоритма, увеличиваются или уменьшаются линейно с числом входов. Линейная сложность обозначается через O(n).
В этом примере давайте напишем простую программу, которая выводит все элементы списка на консоль:
def linear_algo(items):
for item in items:
print(item)
linear_algo([4, 5, 6, 8])
Сложность функции linear_algo в приведенном выше примере линейна, так как число итераций цикла for будет равно размеру входного элемента массива . Например, если в списке items есть 4 элемента, то цикл for будет выполнен 4 раза и так далее.
График линейной сложности с входами по оси x и количеством шагов по оси x выглядит следующим образом:
import matplotlib.pyplot as plt
import numpy as np
x = [2, 4, 6, 8, 10, 12]
y = [2, 4, 6, 8, 10, 12]
plt.plot(x, y, 'b')
plt.xlabel('Inputs')
plt.ylabel('Steps')
plt.title('Linear Complexity')
plt.show()
Выход:
Еще один момент, который следует отметить здесь, заключается в том, что в случае огромного количества входных данных константы становятся незначительными. Например, взгляните на следующий сценарий:
def linear_algo(items):
for item in items:
print(item)
for item in items:
print(item)
linear_algo([4, 5, 6, 8])
В приведенном выше скрипте есть два цикла for, которые повторяются по входному списку items . Поэтому сложность алгоритма становится O(2n), однако в случае бесконечных элементов во входном списке удвоение бесконечности все равно равно бесконечности, поэтому мы можем игнорировать константу 2 (так как она в конечном счете незначительна), и сложность алгоритма остается O(n).
Мы можем дополнительно проверить и визуализировать это, построив входные данные по оси x и количество шагов по оси y, как показано ниже:
import matplotlib.pyplot as plt
import numpy as np
x = [2, 4, 6, 8, 10, 12]
y = [4, 8, 12, 16, 20, 24]
plt.plot(x, y, 'b')
plt.xlabel('Inputs')
plt.ylabel('Steps')
plt.title('Linear Complexity')
plt.show()
В приведенном выше сценарии вы можете ясно видеть, что, однако, вывод является линейным и выглядит следующим образом:
Квадратичная сложность (O(n^2))
Сложность алгоритма называется квадратичной, когда шаги, необходимые для выполнения алгоритма, являются квадратичной функцией количества элементов на входе. Квадратичная сложность обозначается как O(n^2). Взгляните на следующий пример, чтобы увидеть функцию с квадратичной сложностью:
def quadratic_algo(items):
for item in items:
for item2 in items:
print(item, ' ' ,item)
quadratic_algo([4, 5, 6, 8])
В приведенном выше сценарии вы можете видеть, что у нас есть внешний цикл, который повторяет все элементы во входном списке, а затем вложенный внутренний цикл, который снова повторяет все элементы во входном списке. Общее количество шагов, выполненных в * n, где n-количество элементов во входном массиве.
На следующем графике показано количество входов и шагов для алгоритма с квадратичной сложностью.
Нахождение сложности сложных функций
В предыдущих примерах мы видели, что на входе выполняется только одна функция. Что делать, если на входе выполняется несколько функций? Взгляните на следующий пример.
def complex_algo(items):
for i in range(5):
print ("Python is awesome")
for item in items:
print(item)
for item in items:
print(item)
print("Big O")
print("Big O")
print("Big O")
complex_algo([4, 5, 6, 8])
В приведенном выше скрипте выполняется несколько задач, во-первых, строка печатается 5 раз на консоли с помощью оператора print . Затем мы дважды печатаем входной список на экране, и, наконец, еще одна строка печатается три раза на консоли. Чтобы найти сложность такого алгоритма, нам нужно разбить код алгоритма на части и попытаться найти сложность отдельных частей.
Давайте разберем ваш сценарий на отдельные части. В первой части мы имеем:
for i in range(5):
print ("Python is awesome")
Сложность этой части равна O(5). Поскольку в этом фрагменте кода выполняются пять постоянных шагов независимо от входных данных.
Далее, у нас есть:
for item in items:
print(item)
Мы знаем, что сложность приведенного выше фрагмента кода равна O(n).
Аналогично, сложность следующего фрагмента кода также O(n)
for item in items:
print(item)
Наконец, в следующем фрагменте кода строка печатается три раза, следовательно, сложность равна O(3)
print("Big O")
print("Big O")
print("Big O")
Чтобы найти общую сложность, мы просто должны добавить эти индивидуальные сложности. Давайте так и сделаем:
O(5) + O(n) + O(n) + O(3)
Упрощая вышеизложенное, мы получаем:
O(8) + O(2n)
Ранее мы говорили, что когда вход (который в данном случае имеет длину n) становится чрезвычайно большим, константы становятся незначительными, то есть дважды или половина бесконечности все еще остается бесконечностью. Поэтому мы можем игнорировать константы. Конечная сложность алгоритма будет равна O(n).
Сложность худшего и Лучшего случая
Обычно, когда кто-то спрашивает вас о сложности алгоритма, он спрашивает вас о сложности наихудшего случая. Чтобы понять, каков наилучший и худший вариант сложности, посмотрите на следующий сценарий:
def search_algo(num, items):
for item in items:
if item == num:
return True
else:
return False
nums = [2, 4, 6, 8, 10]
print(search_algo(2, nums))
В приведенном выше сценарии у нас есть функция, которая принимает число и список чисел в качестве входных данных. Он возвращает true, если переданное число найдено в списке чисел, в противном случае он возвращает false. Если вы ищете 2 в списке, он будет найден в первом сравнении. Это наилучший случай сложности алгоритма, когда искомый элемент находится в первом искомом индексе. В лучшем случае сложность в этом случае равна O(1). С другой стороны, если вы ищете 10, он будет найден в последнем поисковом индексе. Алгоритм должен будет искать все элементы в списке, поэтому наихудшая сложность становится O(n).
В дополнение к сложности наилучшего и наихудшего случая вы также можете вычислить среднюю сложность алгоритма, которая говорит вам: “Учитывая случайный вход, какова ожидаемая временная сложность алгоритма”?
Сложность пространства
В дополнение к временной сложности, где вы подсчитываете количество шагов, необходимых для завершения выполнения алгоритма, вы также можете найти пространственную сложность, которая относится к количеству пробелов, которые вам нужно выделить в пространстве памяти во время выполнения программы.
Взгляните на следующий пример:
def return_squares(n):
square_list = []
for num in n:
square_list.append(num * num)
return square_list
nums = [2, 4, 6, 8, 10]
print(return_squares(nums))
В приведенном выше скрипте функция принимает список целых чисел и возвращает список с соответствующими квадратами целых чисел. Алгоритм должен выделить память для того же количества элементов, что и во входном списке. Поэтому пространственная сложность алгоритма становится O(n).
Вывод
Обозначение Big-O-это стандартная метрика, используемая для измерения сложности алгоритма. В этой статье мы изучили, что такое нотация Big-O и как ее можно использовать для измерения сложности различных алгоритмов. Мы также изучали различные типы функций Big-O с помощью различных примеров Python. Наконец, мы кратко рассмотрели наихудшую и наилучшую сложность случая вместе с пространственной сложностью.