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

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

(2.4) Предположим, f и g — такие две функции, что для некоторой функции h

выполняются условия f = O(h) и g = O(h). В этом случае f + g = O(h).

Это свойство обобщается для суммы фиксированного числа функций k, где

k может быть больше двух. Точная формулировка результата приведена  ниже;

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

(2.5) Пусть k — фиксированная константа, а f1, f2, …, fk и h — функции, такие что

fi = O(h) для всех i. В этом случае f1 + 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 ). ■

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