Асимптотическая нотация

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

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

Вот формальное определение:

Пусть f(x) и g(x) — функции, определенные в некой окрестности x0, причем g там не обращается в 0.

Тогда f является «O» большим от g при (x -> x0), если существует константа C>0, что для всех x из некоторой окрестности точки x0 имеет место неравенство

|f(x)| <= C |g(x)|

Чуть менее строго:
f является «O» большим от g, если существует константа C>0, что для всех x > x0 

f(x) <= C*g(x)

Не бойтесь формального определения! По сути, оно определяет асимптотическое возрастание времени работы программы, когда количество ваших данных на входе растет в сторону бесконечности. Например, вы сравниваете сортировку массива из 1000 элементов и 10 элементов, и нужно понять, как возрастёт при этом время работы программы. Или нужно подсчитать длину строки символов путем посимвольного прохода и прибавлением 1 за каждый символ:

c - 1 
a – 2
t - 3

Асимптотическая скорость такого "алгоритма" (последовательного прохода по символам) равна О(n), где n — количество букв в слове. Это означает, что если считать по такому принципу, время, необходимое для подсчета всей строки, пропорционально количеству символов. Подсчет количества символов в строке из 20 символов занимает вдвое больше времени, нежели при подсчете количества символов в десятисимвольной строке. 

Представьте, что в переменной length вы сохранили значение, равное количеству символов в строке. Например, length = 1000. Чтобы получить длину строки, нужен только доступ к этой переменной, на саму строку можно даже не смотреть. И как бы мы ни меняли длину, мы всегда можем обратиться к этой переменной. В таком случае асимптотическая скорость = O(1). От изменения входных данных скорость работы в такой задаче не меняется, поиск завершается за постоянное время. В таком случае программа является асимптотически постоянной. 

Недостаток: вы тратите память компьютера на хранение дополнительной переменной и дополнительное время для обновления её значения. 

Если вам кажется, что линейное время — это плохо, смеем заверить: бывает гораздо хуже. Например, O(n2). Такая запись означает, что с ростом n рост времени, нужного для перебора элементов (или другого действия) будет расти всё резче. 

При маленьких n алгоритмы с асимптотической скоростью O(n2) могут работать быстрее, чем алгоритмы с асимптотикой О(n). 

Но в какой-то момент квадратичная функция обгонит линейную, от этого не уйти. 

Еще одна асимптотическая сложность — логарифмическое время или O(log n). С ростом n эта функция возрастает очень медленно. О(log n) — время работы классического алгоритма бинарного поиска в отсортированном массиве (помните разорванный телефонный справочник на лекции?). Массив делится надвое, затем выбирается та половина, в которой находится элемент и так, каждый раз уменьшая область поиска вдвое, мы ищем элемент. 

Что будет, если мы сразу наткнемся на искомое, разделив в первый раз наш массив данных пополам? Для лучшего времени есть термин — Омега-большое или Ω(n).

В случае бинарного поиска = Ω(1) (находит за постоянное время независимо от размера массива). 

Линейный поиск работает за время O(n) и Ω(1), если искомый элемент — самый первый. 

Еще один символ — тета (Θ(n)). Он используется, когда лучший и худший варианты одинаковы. Это подходит для примера, где мы хранили длину строки в отдельной переменной, поэтому при любой её длине достаточно обратиться к этой переменной. Для этого алгоритма лучший и худший варианты равны соответственно Ω(1) и O(1). Значит, алгоритм работает за время Θ(1).