«1. Обзор

В этом уроке мы поговорим о том, что означает нотация Big O. Мы рассмотрим несколько примеров, чтобы исследовать их влияние на время выполнения вашего кода.

2. Интуиция нотации Big O

Мы часто слышим о производительности алгоритма, описанного с использованием нотации Big O.

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

Мы будем рассматривать время как ресурс. Как правило, чем меньше времени требуется алгоритму для завершения, тем лучше.

3. Алгоритмы с постоянным временем — O(1)

Как размер входных данных алгоритма влияет на время его работы? Ключом к пониманию Big O является понимание скорости, с которой все может расти. Здесь речь идет о времени, затраченном на размер ввода.

Рассмотрим этот простой фрагмент кода: 

int n = 1000;
System.out.println("Hey - your input is: " + n);

Понятно, что не имеет значения, что такое n выше. Этот фрагмент кода требует постоянного времени для выполнения. Это не зависит от размера n.

Аналогично: 

int n = 1000;
System.out.println("Hey - your input is: " + n);
System.out.println("Hmm.. I'm doing more stuff with: " + n);
System.out.println("And more: " + n);

Вышеприведенный пример также является постоянным временем. Даже если это займет в 3 раза больше времени, это не зависит от размера входных данных, n. Мы обозначаем алгоритмы с постоянным временем следующим образом: O(1). Обратите внимание, что O(2), O(3) или даже O(1000) означают одно и то же.

Нас не волнует точное время выполнения, важно только то, что это занимает постоянное время.

4. Алгоритмы логарифмического времени — O(log n)

Алгоритмы с постоянным временем (асимптотически) самые быстрые. Логарифмическое время является следующим самым быстрым. К сожалению, их немного сложнее представить.

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

Здесь важно то, что время работы растет пропорционально логарифму входных данных (в данном случае логарифмирование по основанию 2): 

for (int i = 1; i < n; i = i * 2){
    System.out.println("Hey - I'm busy looking at: " + i);
}

Если n равно 8, вывод будет следующим : 

Hey - I'm busy looking at: 1
Hey - I'm busy looking at: 2
Hey - I'm busy looking at: 4

Наш простой алгоритм выполнил log(8) = 3 раза.

5. Алгоритмы с линейным временем — O(n)

После алгоритмов с логарифмическим временем мы получаем следующий самый быстрый класс: алгоритмы с линейным временем.

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

Подумайте о простом цикле for: 

for (int i = 0; i < n; i++) {
    System.out.println("Hey - I'm busy looking at: " + i);
}

Сколько раз выполняется этот цикл for? n раз, конечно! Мы не знаем точно, сколько времени это займет, и мы не беспокоимся об этом.

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

Мы бы предпочли время выполнения 0,1n, чем (1000n + 1000), но оба алгоритма по-прежнему являются линейными; они оба растут прямо пропорционально размеру их вложений.

Опять же, если бы алгоритм был изменен на следующий: 

for (int i = 0; i < n; i++) {
    System.out.println("Hey - I'm busy looking at: " + i);
    System.out.println("Hmm.. Let's have another look at: " + i);
    System.out.println("And another: " + i);
}

Время выполнения по-прежнему было бы линейным по размеру входных данных, n. Обозначим линейные алгоритмы следующим образом: O(n).

Как и в случае с алгоритмами с постоянным временем, нас не волнуют особенности среды выполнения. O(2n+1) — это то же самое, что и O(n), поскольку нотация Big O связана с ростом размеров входных данных.

6. Алгоритмы N Log N Time — O(n log n)

n log n — следующий класс алгоритмов. Время выполнения увеличивается пропорционально n log n входных данных: 

for (int i = 1; i <= n; i++){
    for(int j = 1; j < n; j = j * 2) {
        System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
    }
}

Например, если n равно 8, то этот алгоритм будет выполняться 8 * log(8) = 8 * 3 = 24 раза. Есть ли у нас строгое неравенство или нет в цикле for, не имеет значения для нотации Big O.

7. Алгоритмы с полиномиальным временем — O(np)

Далее у нас есть алгоритмы с полиномиальным временем. Эти алгоритмы еще медленнее, чем алгоритмы n log n.

Термин полином является общим термином, который включает квадратичные (n2), кубические (n3), четвертые (n4) и т. д. функции. Важно знать, что O(n2) быстрее, чем O(n3), который быстрее, чем O(n4) и т. д.

Давайте рассмотрим простой пример алгоритма квадратичного времени: 

for (int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
        System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
    }
}

~~ ~»

«Этот алгоритм будет выполняться 82 = 64 раза. Обратите внимание: если бы мы вложили еще один цикл for, это стало бы алгоритмом O (n3).

8. Алгоритмы экспоненциального времени — O(kn)

Теперь мы вступаем на опасную территорию; эти алгоритмы растут пропорционально некоторому коэффициенту, возведенному в степень от размера входных данных.

Например, алгоритмы O(2n) удваиваются с каждым дополнительным вводом. Итак, если n = 2, эти алгоритмы будут выполняться четыре раза; если n = 3, они будут выполняться восемь раз (что-то вроде противоположности алгоритмам логарифмического времени).

O(3n) алгоритмов утраивается с каждым дополнительным входом, O(kn) алгоритмов будет увеличиваться в k раз с каждым дополнительным входом. 

for (int i = 1; i <= Math.pow(2, n); i++){
    System.out.println("Hey - I'm busy looking at: " + i);
}

Давайте рассмотрим простой пример алгоритма времени O(2n):

Этот алгоритм будет выполняться 28 = 256 раз.

9. Алгоритмы факториального времени — O(n!)

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

Классический пример — решение задачи о коммивояжере методом грубой силы.

Объяснение решения задачи о коммивояжере выходит за рамки этой статьи. 

for (int i = 1; i <= factorial(n); i++){
    System.out.println("Hey - I'm busy looking at: " + i);
}

Вместо этого давайте рассмотрим простой алгоритм O(n!), как и в предыдущих разделах:

где factorial(n) просто вычисляет n!. Если n равно 8, этот алгоритм будет работать 8! = 40320 раз.

10. Асимптотические функции

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

Big O не заботится о том, насколько хорошо ваш алгоритм работает с входными данными небольшого размера. Это связано с большими входными данными (подумайте о сортировке списка из миллиона чисел по сравнению с сортировкой списка из 5 чисел).

Следует также отметить, что существуют и другие асимптотические функции. Big Θ (тета) и Big Ω (омега) также описывают алгоритмы на пределе (помните, предел это означает только для огромных входных данных).

Чтобы понять разницу между этими тремя важными функциями, нам сначала нужно знать, что каждая из Big O, Big Θ и Big Ω описывает набор (то есть набор элементов).

    Здесь членами наших наборов являются сами алгоритмы:

Big O описывает множество всех алгоритмов, которые работают не хуже определенной скорости (это верхняя граница) И наоборот, Big Ω описывает множество всех алгоритмов которые работают не лучше определенной скорости (это нижняя граница) Наконец, Big Θ описывает набор всех алгоритмов, которые работают с определенной скоростью (это как равенство)

Определения, которые мы дали выше, не являются математически точными , но они помогут нашему пониманию.

Обычно вы слышите о вещах, описываемых с помощью Big O, но не помешает узнать о Big Θ и Big Ω.

11. Заключение

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

Прекрасную визуализацию различных классов сложности можно найти здесь.