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

Также полезно иметь количественную оценку эффекта суммирования двух функций. Прежде всего, если имеется асимптотическая верхняя оценка, применимая к каждой из двух функций 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). 

Это свойство обобщается для суммы фиксированного числа функций 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 ). ■

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