Главная » Ядро Linux » Множество О

0

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

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

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

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

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии