Т ранзитивность

Первое свойство — транзитивность: если функция f асимптотически ограничена сверху функцией g, а функция g, в свою очередь, асимптотически ограничена сверху функцией h, то функция f асимптотически ограничена сверху функцией h.
Аналогичное свойство действует и для нижних границ. Более точно это можно записать в следующем виде.

(2.2)

(a) Если f = O(g) и g = O(h), то f = O(h).

(b) Если f = Ω(g) и g = Ω(h), то f = Ω(h).

Доказательство. Мы ограничимся частью (а) этого утверждения; часть (б) до- казывается практически аналогично.

Для (а) известно, что для некоторых констант c и n0 выполняется условие f (n) < cg(n) для всех n > n0. Кроме того, для некоторых (возможно, других) констант c' и n0' выполняется условие g(n) < c'h(n) для всех n > n0'. Возьмем любое число n, не меньшее как n0, так и n0'. Известно, что f (n) < cg(n) < cc'h(n), поэтому f (n) < cc'h(n) для всех n > max(n0, n0'). Из последнего неравенства следует, что f = O(h). ■

Объединяя части (a) и (b) в (2.2), можно прийти к аналогичному результату для асимптотически точных границ. Допустим, известно, что f = Θ^), а g = Θ(Η). Так как f = O(g) и g = O(h), из части (а) известно, что f = O(h); а поскольку f= Ω(g) и g = Ω(h), из части (б) следует, что f = Ω(h). Таким образом, f= Θ^). Следовательно, мы показали, что

(2.3) Если f = θ⅛) и g = Θ^), то f= Θ^).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Т ранзитивность:

  1. Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
  2. ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
  3. ПЕРЕДМОВА
  4. Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
  5. Розділ І. Загальні положення цивільного права
  6. Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
  7. Тема 2. Цивільне законодавство України
  8. Тема 3. Поняття, елементи та види цивільних правовідносин
  9. Тема 4. Здійснення цивільних прав і виконання обов’язків
  10. Тема 5. Захист цивільних прав та інтересів