Книга: Разработка ядра Linux

Множество О

Множество О

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

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

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

Оглавление книги