Разбор временной сложности алгоритма: оценка эффективности

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

В данной статье рассмотрим ключевые аспекты, такие как «O-нотация», которая позволяет формализовать и сравнивать различные алгоритмы с точки зрения их временной сложности.

Анализ алгоритмов

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

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

Например, ниже представлен алгоритм на языке Python, который считает от 1 до 5 и отображает каждое число:

for i in range(1, 6):
    print(i)

Вы можете измерить время выполнения данного алгоритма, используя встроенный в Python модуль time. С помощью этого модуля можно определить, сколько времени занимает выполнение алгоритма на вашем компьютере.

При запуске программы происходит вывод чисел от 1 до 5, сопровождаемый отображением затраченного времени на выполнение операции. В моем конкретном случае программа завершила свою работу за 0.002 секунды.

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

Кроме того, время выполнения алгоритма будет отличаться при использовании его на разных компьютерах. На машине с более низкой вычислительной мощностью алгоритм будет выполняться медленнее, а на более мощной — быстрее. Также на время выполнения влияет выбранный язык программирования. Например, алгоритм, реализованный на языке C++, скорее всего, будет выполняться быстрее, чем аналогичный алгоритм на Python, из-за различий в скорости выполнения этих языков.

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

Вернемся к примеру с программой, выводящей числа от 1 до 5:

for i in range(1, 6):
    print(i)

Этой программе требуется пять шагов для завершения (она проходит цикл пять раз и выводит i каждый раз) и это можно выразить уравнением [math]f(n) = 5[/math].

Если усложнить программу, то уравнение изменится. Например, вы можете захотеть отслеживать сумму всех выводимых цифр:

count = 0
for i in range(1, 6):
    print(i)
    count += i

Теперь алгоритму требуется выполнить 11 шагов для завершения. Сначала он присваивает переменной count нулевое значение. Затем выводит пять чисел и пять раз инкрементируется (1 + 5 + 5 = 11).

Вот новое уравнение для этого алгоритма:

[math]f(n) = 11[/math]

Что произойдет, если вы замените 6 на переменную?

count = 0
for i in range(1, n):
    print(i)
    count += i

Уравнение приобретет следующий вид:

[math]f(n) = 1 + 2n[/math]

Теперь количество шагов алгоритма зависит от значения [math]n[/math]. Цифра 1 в уравнении представляет первый шаг: count = 0. Затем следуют два шага с переменной [math]n[/math]. Например, если [math]n = 5, f(n) = 1 + 2 × 5[/math]. Программисты называют переменную n в уравнении, которое описывает количество шагов в алгоритме, размером задачи. В данном случае вы можете сказать, что время на решение задачи размером [math]n[/math] равно [math]1 + 2n[/math], или то же самое в математическом обозначении:

[math]T(n) = 1 + 2n[/math].

Уравнение, описывающее количество шагов в данном алгоритме, не сильно помогает, так как, помимо всего прочего, вы не можете достоверно посчитать количество шагов в алгоритме. Например, если алгоритм содержит много условных операторов и вы не в состоянии заранее предугадать, какие из них будут исполнены. Хорошая новость в том, что для вас как для программиста не имеет значения точное количество шагов алгоритма — вам важно знать, как алгоритм поведет себя при увеличении переменной [math]n[/math]. Большинство алгоритмов хорошо работают с малым объемом данных, но могут не справиться с большим. Даже самый неэффективный алгоритм будет хорошо работать при [math]n = 1[/math]. Однако в реальности n, равное единице, встречается редко: значение переменной может составлять и несколько сотен тысяч, и миллион, и даже более.

Что действительно необходимо знать об алгоритме — не точное, а, скорее, приблизительное количество шагов, которое потребуется при увеличении [math]n[/math]. Когда [math]n[/math] возрастает, одна часть уравнения затмевает другую до такой степени, что все остальное становится просто неактуальным.

Посмотрите на следующий код Python:

def print_it(n):
    # цикл 1
    for i in range(n):
        print(i)
    # цикл 2
    for i in range(n):
        print(i)
        for j in range(n):
            print(j)
            for h in range(n):
                print(h)

Какая часть этой программы наиболее важна для определения количества шагов, необходимых алгоритму для завершения? Вы можете предположить, что обе части функции (первый цикл и второй цикл, содержащий другие циклы) важны. В конце концов, если [math]n[/math] равно [math]10 000[/math], ваш компьютер выведет много чисел в обоих циклах.

Получается, что данный код не подходит, если говорить об эффективности алгоритма:

# цикл 1
for i in range(n):
    print(i)

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

[math]T(n) = n + n^3[/math]

Когда у вас два вложенных цикла for с количеством шагов [math]n[/math], они преобразуются в [math]n^2[/math], потому что если [math]n[/math] равно [math]10[/math], то вам необходимо выполнить [math]10[/math] шагов дважды, или [math]10^2[/math]. Три вложенных цикла for всегда преобразуются в [math]n^3[/math] по той же причине. В данном уравнении, когда [math]n[/math] равно 10, первому циклу вашей программы потребуется [math]10[/math] шагов, а второму циклу потребуется [math]10^3[/math]шагов, что равно [math]1000[/math]. Когда [math]n[/math] равно [math]1000[/math], первому циклу требуется [math]1000[/math] шагов, а второму циклу необходимо [math]1000^3[/math], что равно 1 миллиарду.

Видите, что происходит? По мере роста [math]n[/math] вторая часть вашего алгоритма растет намного быстрее, поэтому первая часть становится неактуальной. Например, если вам необходимо, чтобы программа работала для [math]100 000 000[/math] записей базы данных, вас не будет волновать количество шагов в первой части, так как шаги во второй части будут расти в геометрической прогрессии. При наличии [math]100 000 000[/math] записей вторая часть алгоритма будет состоять из более чем септиллиона шагов, то есть 1 с 24 нулями, поэтому использовать данный алгоритм не имеет смысла. Первые [math]100 000 000[/math] шагов нерелевантны для вас при принятии решения.

Поскольку важной частью алгоритма является та часть, которая растет быстрее по мере увеличения [math]n[/math], для описания эффективности алгоритма программисты вместо равенства [math]T(n)[/math] используют нотацию «O большое». Нотация «O большое» — это математическое обозначение, описывающее, как по мере роста  [math]n[/math] возрастают требования алгоритма к времени и объему памяти (о требованиях к объему вы узнаете позднее).

Программисты используют нотацию «О большое» для создания функции порядка величины [math]T(n)[/math]. Порядок величины — тип объекта в системе классификации, в которой каждый тип во много раз больше или меньше предыдущего. В функции порядка величины вы используете ту часть [math]T(n)[/math], которая преобладает в уравнении, и игнорируете все остальное. Часть [math]T(n)[/math], преобладающая в уравнении, — это порядок величины алгоритма.

Ниже представлены общепринятые классификации порядка величины для нотации
«О большое»: от наилучшего (наиболее эффективного) до наихудшего (наименее эффективного):

1. Постоянное время
2. Логарифмическое время
3. Линейное время
4. Линейно-логарифмическое время
5. Квадратичное время
6. Кубическое время
7. Экспоненциальное время

Каждый порядок величины описывает временн ю сложность алгоритма. 
Временная сложность — это максимальное количество шагов, требующихся алгоритму для завершения по мере увеличения [math]n[/math].

Рассмотрим подробнее каждый порядок величины.

Постоянное время

Наиболее эффективным порядком величины является постоянная временная сложность. Алгоритм выполняется за постоянное время, когда ему требуется одно и то же количество шагов вне зависимости от объема задачи. Нотация «О большое» для постоянной сложности — [math]О(1)[/math].

Допустим, у вас онлайн-магазин книг и каждый день вы дарите книгу первому покупателю. Вы храните своих покупателей в списке customers. Алгоритм может выглядеть следующим образом:

free_books = customers[0] 

А равенство [math]T(n)[/math] выглядит так:

[math]T(n) = 1 [/math]

Вашему алгоритму требуется один шаг независимо от количества покупателей. Если у вас [math]1000[/math] покупателей, алгоритму необходим один шаг. Если у вас [math]10 000[/math] покупателей, вашему алгоритму все еще требуется один шаг, и даже если у вас триллион покупателей, все равно алгоритм завершится в один шаг.

Если изобразить на графике постоянную временную сложность, где по оси [math]Х[/math] отображается количество покупателей, по оси [math]Y[/math] — количество шагов, линия на графике будет ровной.

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

Логарифмическое время

Логарифмическое время — вторая по эффективности временная сложность. Алгоритм выполняется за логарифмическое время, когда время выполнения программы растет пропорционально логарифму размера входных данных. Подобную временную сложность можно увидеть в таких алгоритмах, как двоичный поиск, который может не учитывать множество значений в каждом цикле. Логарифмический алгоритм в нотации «О большое» выражается как [math]О(log_n) [/math]

В логарифмическом алгоритме количество необходимых шагов по мере увеличения набора данных растет достаточно медленно.

Линейное время

Следующий по эффективности тип алгоритма — тот, который выполняется за линейное время. Такой алгоритм растет пропорционально росту размера задачи. Линейный алгоритм в нотации «О большое» выражается как [math]О(n)[/math].

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

free_book = False
customers = ["Мухаммад", "Шамиль", "Наталия", "Юлия", "Марьям", "Зураб"]
for customer in customers:
    if customer[0] == "М":
        print(customer)

Когда список покупателей состоит из пяти позиций, программе для завершения требуется осуществить пять шагов. Для списка из 10 покупателей программе потребуется 10 шагов, для 20 покупателей — 20 шагов и т. д.

Ниже приведено уравнение для временной сложности данной программы:

[math]f(n) = 1 + 1 + n[/math]

А в нотации «О большое» вы можете не учитывать константы и сфокусироваться на части, преобладающей в уравнении

[math]O(n) = n[/math]

В линейном алгоритме по мере роста [math]n[/math] количество шагов алгоритма увеличивается на то же количество, что и [math]n[/math]

Линейно-логарифмическое время

Алгоритм, выполняющийся за линейно-логарифмическое время, растет как сочетание (умножение) логарифмических и линейных временных сложностей. Например, линейно-логарифмический алгоритм может вычислять операцию [math]O(\log n)[/math] [math]n[/math] раз.

В нотации «О большое» линейно-логарифмический алгоритм выражается как [math]O(n \log n)[/math]. Линейно-логарифмические алгоритмы часто разделяют набор данных на меньшие части и каждую из них обрабатывают по отдельности. Например, большинство наиболее эффективных алгоритмов сортировки, с которыми вы познакомитесь далее, такие как сортировка слиянием, являются линейно логарифмическими.

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

Квадратичное время

Следующим по эффективности после линейно-логарифмического идет квадра- тичное время. Алгоритм выполняется за квадратичное время, когда его произ- водительность прямо пропорциональна размеру задачи в квадрате. В нотации «О большое» квадратичный алгоритм выражается как [math]О(n^2)[/math].

Ниже приведен пример квадратичной временн й сложности.

numbers = [1, 2, 3, 4, 5]
for i in numbers:
    for j in numbers:
        x = i * j
        print(x)  

Алгоритм умножает каждое число из списка чисел на каждое следующее число, сохраняет результат в переменной и выводит его на экран. В данном случае [math]n[/math]—это размер вашего списка numbers.

Уравнение для временной сложности алгоритма следующее:

[math]f(n) = 1 + n \cdot n \cdot (1 + 1)[/math]

В этом уравнении [math](1 + 1)[/math] является результатом умножения и вывода. Вы повторяете умножение и вывод [math]n \cdot n[/math] раз с двумя вложенными циклами for.

Можно упростить уравнение:

[math]f(n) = 1 + (1 + 1) \cdot n^2[/math]

Что идентично следующему:

[math]f(n) = 1 + 2 \cdot n^2[/math]

Как вы уже могли догадаться, преобладает часть уравнения n^2, поэтому в нотации «О большое» равенство будет таким:

[math]O(n) = n^2[/math]

На графике алгоритма с квадратичной временной сложностью количество шагов резко увеличивается по мере увеличения размера задачи.

Как правило, если ваш алгоритм содержит два вложенных цикла, выполняемых от [math]1[/math] до [math]n[/math]( или от [math]0[/math] до [math]n–1[/math]), временная сложность будет как минимум [math]О(n^2)[/math]. Большинство алгоритмов сортировки, такие как сортировка методом вставок или пузырьковая сортировка, выполняются за квадратичное время.

Кубическое время

За квадратичной временной сложностью следует кубическая. Алгоритм выполняется за кубическое время, когда производительность прямо пропорциональна размеру задачи в кубе. В нотации «О большое» вы выражаете кубический алгоритм как [math]О(n^3)[/math]. Алгоритм с кубической сложностью похож на квадратичный, только [math]n[/math] возводится в третью степень, а не во вторую.

Ниже представлен алгоритм с кубической временной сложностью:

numbers = [1, 2, 3, 4, 5]
for i in numbers:
    for j in numbers:
        for h in numbers:
            x = i + j + h
            print(x)

Уравнение для этого алгоритма следующее:

[math]f(n) = 1 + n \cdot n \cdot n \cdot (1 + 1)[/math]

Или же:

[math]f(n) = 1 + 2 \cdot n^3[/math]

Как и в алгоритме с квадратичной сложностью, наиболее важная часть данного уравнения — [math]n^3[/math], которая растет так быстро, что остальная часть уравнения, даже та, что включает в себя  [math]n^2[/math], становится нерелевантной. Таким образом, в нотации «О большое» кубическая сложность выглядит так:

[math]O(n) = n^3[/math]

Два вложенных цикла свидетельствуют о квадратичной временной сложности, а три вложенных цикла, выполняемых от [math]0[/math] до [math]n[/math], — признак алгоритма с кубическим временем. Весьма вероятно, что вы столкнетесь с кубической временн й сложностью, если ваша работа связана с data science или статистикой.

И квадратичная, и кубическая временн е сложности представляют собой частные случаи полиномиальной временной сложности. Алгоритм, который выполняется за полиномиальное время, вычисляется как [math]О(n^а)[/math], где [math]а = 2[/math] для квадратичного времени и [math]а = 3[/math] для кубического времени. При создании алгоритма, как правило, пытаются избежать полиномиального масштабирова- ния, потому что алгоритм может работать очень медленно при увеличении [math]n[/math]. Иногда избежать полиномиального масштабирования не получается, но в таком случае вы можете успокаивать себя тем, что полиномиальная сложность — еще не самый худший вариант.

Экспоненциальное время

Гордый титул «наихудшая временная сложность» по праву принадлежит экспоненциальной. Алгоритм, который выполняется за экспоненциальное время, содержит константу, увеличенную до размеров задачи. Другими словами, алгоритму с экспоненциальным временем для завершения требуется с шагов, возведенных в степень [math]n[/math]. Нотация «О большое» для экспоненциального времени равна [math]О(с^n)[/math], где [math]с[/math] — это константа. Значение константы не играет роли. Важно лишь то, что [math]n[/math] находится в экспоненте.

К счастью, экспоненциальная сложность встречается не так часто. Одним из примеров данной сложности, связанной с попыткой угадать числовой пароль из [math]n[/math]-го количества десятичных знаков путем проверки всех возможных комбинаций, является [math]О(10^n)[/math].

Ниже приведен пример угадывания пароля со сложностью [math]О(10^n)[/math]:

pin = "45781"
n = len(pin)
for i in range(10**n):
    if str(i) == pin:
        print(i)

Количество шагов, необходимых этому алгоритму для завершения, растет с невероятной скоростью по мере увеличения [math]n[/math]. Когда [math]n[/math] равно [math]1[/math], алгоритму требуется [math]10[/math] шагов. Когда [math]n[/math] равно [math]2[/math], необходимо [math]100[/math] шагов. Когда [math]n[/math] равно [math]3[/math], будет затрачено [math]1000[/math] шагов. Как вы можете заметить, сначала кажется, что экспоненциальный алгоритм растет не так уж и быстро. Но в конце концов рост становится взрывным. Для угадывания пароля из [math]8[/math] десятичных цифр потребуется [math]100[/math] миллионов шагов, а чтобы угадать пароль из [math]10[/math] десятичных знаков, придется выполнить более [math]10[/math] миллиардов шагов. Экспоненциальное масштабирование позволяет понять, почему так важно создавать длинные пароли. Если кто-то попытается отгадать ваш пароль с помощью подобной программы, он с легкостью это сделает для пароля из четырех знаков. Однако пароль из 20 знаков взломать невозможно, потому что программа будет выполняться дольше, чем человек живет на свете.

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

На последнем графике представлено сравнение эффективности рассмотренных видов алгоритмов.