Практические Java-примеры нотации Big O

1. Обзор

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

2. Интуиция нотации большого O

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

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

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

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(n p )

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

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

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

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);
    }
}

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

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

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

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

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

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

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

Этот алгоритм будет работать 2 8 = 256 раз.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как обычно, фрагменты кода для этого руководства можно найти на GitHub .