Роберт Лав - Разработка ядра Linux

y=f(x)

В этом выражении буквой yобозначено время подсчета количества людей в комнате.

Полезным обозначением асимптотического поведения функции является верхняя граница — функция, значения которой всегда больше значений изучаемой функции. Говорят, что верхняя граница некоторой функции растет быстрее, чем рассматриваемая функция. Специальное обозначение "большого-O" используется для описания этого роста. Это записывается как f ( x ) ∈ О ( g ( x )) и читается так: f принадлежит множеству "O-большого" от g . Формальное математическое определение имеет следующий вид.

Если f ( x ) принадлежит множеству большого O ( g ( x )) , то ∃ c и x ', такие что f ( x )≤c∙ g ( x ), ∀ x > x '

Это означает, что время вычисления функции f ( x ) всегда меньше времени вычисления функции g ( x ), умноженного на некоторую константу, и это справедливо всегда, для всех значений x , больших некоторого начального значения х '.

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

Когда говорят об обозначении большого-О, то чаще всего имеют в виду то, что Дональд Кнут (Donald Knuth) описывал с помощью обозначения "большого-тета". Обозначение "большого-О" соответствует верхней границе. Например, число 7 — это верхняя граница числа 6, кроме того, числа 9, 12 и 65 — это тоже верхние границы числа 6. Когда рассматривают рост функции, то обычно наиболее интересна наименьшая верхняя граница или функция, которая моделирует как верхнюю, так и нижнюю границу [100] Если интересно, то нижняя граница описывается с помощью обозначения большого-омега. Определение аналогично определению множества большого-О, за исключением того, что значения функции g ( x ) должны быть меньше значений функции f ( x ) или равны им. . Профессор Кнут описывает это с помощью обозначения большого-тета следующим образом.

Если f ( x ) принадлежит множеству большого-тета от g ( x ), то g ( x ) является одновременно и верхней и нижней границей f ( x )

Можно также сказать, что функция f ( x ) порядка функции g ( x ). Порядок, или множество "большого-тета" алгоритма, — один из наиболее важных математических инструментов изучения алгоритмов.

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

Вернемся снова к подсчету количества людей в комнате. Допустим, что можно считать по одному человеку за секунду. Следовательно, если в комнате находится 7 человек, то подсчет займет 7 секунд. Очевидно, что если будет n человек, то подсчет всех займет n секунд. Поэтому можно сказать, что этот алгоритм масштабируется, как O ( n ). Что если задача будет состоять в том, чтобы станцевать перед всеми, кто находится в комнате? Поскольку, независимо от того, сколько человек будет в комнате, это займет одно и то же время, значит, этот алгоритм масштабируется, как O (1). В табл. В.1 показаны другие часто встречающиеся характеристики сложности.

Таблица В.1. Значения масштабируемости алгоритмов во времени

Как масштабируется алгоритм представления всех людей в комнате друг другу? Какая функция может промоделировать этот алгоритм? Для представления одного человека необходимо 30 секунд, сколько времени займет представление 10 человек друг другу? Что будет в случае 100 человек?

Очевидно, что будет разумным избегать алгоритмов, которые масштабируются, как О ( n !) или O (2ⁿ). Более того, замена алгоритма, который масштабируется, как O ( n ), алгоритмом, который масштабируется, как O (1), — это обычно серьезное улучшение. Тем не менее это не всегда так, и нельзя принимать решение вслепую, базируясь только на описании "большого-О". Вспомните, что в определении множества О ( g ( x )) фигурирует константа, на которую умножается значение функции g ( x ). Поэтому есть возможность, что алгоритм, который масштабируется, как O ( 1 ), будет выполняться в течение 3 часов. Следовательно, он будет выполняться всегда в течение 3 часов, независимо от количества входных данных, но это может оказаться дольше, по сравнению с алгоритмом, который масштабируется, как O ( n ), при небольшом количестве входных данных. При сравнении алгоритмов необходимо всегда принимать во внимание количество входных данных. Не стоит слепо оптимизировать для некоторого случайно выбранного варианта.