«O» большое и «o» малое

Примеры

Во всех следующих примерах используется код, написанный на языке Python. Обратите внимание, что это не полный список типов Big O.

Постоянный

O ( 1 ) {\displaystyle O(1)} . Всегда занимает одинаковое количество времени независимо от ввода. Например, возьмем функцию, которая принимает целое число (вызывается x) и возвращает двойное значение:

После принятия входа эта функция всегда будет выполнять один шаг для возврата выхода. Она является постоянной, потому что всегда будет занимать один и тот же промежуток времени, так что это O ( 1 ) {\displaystyle O(1)} .

Линейный

O ( n ) {\displaystyle O(n)} . Увеличивается в соответствии с размером входного сигнала, представленного n {\displaystyle n} . Предположим, что функция принимает n и возвращает каждое число от 1 до n:

Если бы мы вводили значение 5, то это вывело бы 1,2,3,4,5 {\displaystyle 1,2,3,4,5}. требующий 5 петель для завершения. Аналогично, если мы введем 100, то получим 1,2,3...98,99,100 {\displaystyle 1,2,3...98,99,100} , для завершения которых требуется 100 петель. Если вход n {\displaystyle n}, то время выполнения алгоритма каждый раз ровно n {\displaystyle n} циклов, поэтому это O ( n ) {\displaystyle O(n)} .

Факториал

O ( n ! ) {\displaystyle O(n!)} . Увеличивает факториальные величины, т.е. время, затрачиваемое на ввод, значительно увеличивается. Например, скажем, мы хотим посетить пять городов по всему миру и хотим увидеть все возможные порядки (перестановки). Алгоритм, который мы могли бы написать, используя библиотеку Python's itertools, следующий:

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

("Лондон", "Париж", "Берлин", "Амстердам", "Рим") ("Лондон", "Париж", "Берлин", "Рим", "Амстердам") ("Лондон", "Париж", "Амстердам", "Берлин", "Рим") ... ("Рим", "Амстердам", "Париж", "Берлин", "Лондон") ("Рим", "Амстердам", "Берлин", "Лондон", "Париж") ("Рим", "Амстердам", "Берлин", "Париж", "Лондон")

Здесь наш список входов состоит из 5 пунктов, а для каждого из них наши остальные пункты уменьшаются на 1. Другими словами, наши 5 входов выбирают 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} пунктов (или 5 ! {\displaystyle 5!} ). Если наш вход n {\displaystyle n} длинный город, то количество выходов n ! {\displaystyle n! } ; другими словами, предполагая, что мы пройдем через каждую перестановку, нам понадобится O ( n ! ) {\displaystyle O(n!)} циклов для ее завершения.

Маленькая запись

Более строгая версия "Большой О" - маленькая. Разница между большим О и малым О заключается в том, что малый О - это строгая верхняя граница: если О ( n ) {\displaystyle O(n)} означает, что время завершения увеличится до этого максимума в зависимости от размера входного файла, то о ( n ) {\displaystyle o(n)} означает, что время завершения, как правило, будет меньше этого количества времени. Другими словами, Big O предполагает, что каждый цикл будет проходить по самому длинному пути и процесс займет как можно больше времени, в то время как little-o более реалистично относится к реальному времени выполнения; если количество циклов основано на бросании 6-тигранной кости, то Big O всегда будет считать, что брошена 6-тигранная кость, в то время как little-o будет учитывать одинаковую вероятность броска других чисел.