Суммы функций

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

(2.4) Предположим, f и g — такие две функции, что для некоторой функции h выполняются условия f = O(h) и g = O(h). В этом случае f + g = O(h).

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

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

доказательство не приводится, так как оно, по сути, повторяет доказательство (2.4) для сумм, состоящих из к слагаемых вместо 2.

(2.5) Пусть к — фиксированная константа, аfv f2, ..., fk и h — функции, такие что f = O(h) для всех i. В этом случаеf + f2 + ...+fk = O(h).

У (2.4) имеется следствие, которое проявляется в типичной ситуации: во время анализа алгоритма, состоящего из двух высокоуровневых частей, часто удается легко показать, что одна из двух частей медленнее другой. В этом случае время выполнения всего алгоритма асимптотически сравнимо со временем выполнения медленной части. Поскольку общее время выполнения представляет собой сумму двух функций (время выполнения двух частей), полученные выше результаты для асимптотических границ сумм функций напрямую применимы в данном случае.

(2.6) Предположим, f и g — две функции (получающие неотрицательные значе- ния) и g = O(f). В этом случаеf + g = Θ(f). Другими словами, f является асимпто- тически точной границей для объединенной функции f + g.

Доказательство. Очевидно, f + g = Ω( f), так как для всех n > 0 выполняется условие f(n) + g(n) > f (n). Чтобы завершить доказательство, необходимо показать, что f + g = O( f).

Но это утверждение является прямым следствием (2.4): дано, что g = O( f), а условие f = O(f) выполняется для любой функции, поэтому из (2.4) следует f + g = O( f). ■

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

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

Еще по теме Суммы функций:

  1. Функции журналистики. Понятие функцию Многообразие социальных и информационных потребностей общества – объективная основа функций журналистики.
  2. 1.3.4. Отчисления из суммы заработной платы
  3. 1.3. ОПЛАТА ТРУДА, ОТЧИСЛЕНИЯ ИЗ СУММЫ ЗАРАБОТНОЙ ПЛАТЫ
  4. Статья 448. Право автора на часть от суммы продажи оригинала произведения
  5. Статья 535. Увеличение суммы, которая выплачивается физическому лицу по денежным обязательствам
  6. “Не язык — функция поэта, а поэт — функция языка”
  7. 1.1.2. Функции социологии
  8. РЕЧЬ: ФУНКЦИЯ ПРЕДИКАТИВНАЯ
  9. ФУНКЦИЯ ПСИХИЧЕСКАЯ НАТУРАЛЬНАЯ
  10. ФУНКЦИЯ ПСИХОФИЗИОЛОГИЧЕСКАЯ
  11. Иерархия функций
  12. Функции управления в организации.