Сложение и умножение в O-символике
Правило суммы. Если и , то . (Аналогичные утверждения справедливы также для множеств и ).
Доказательство. (Доказательство этой теоремы основывается простом соотношении для произвольных вещественных чисел , , , : если и , то )
Поскольку , существует константа с1 и неотрицательное целое число n1 такие, что для всех справедливо .
По аналогии, поскольку существует константа и неотрицательное целое число такие, что для всех справедливо .
Обозначим через и рассмотрим случай, когда верны оба неравенства для случая . Сложив приведенные выше неравенства, получим
.
Откуда следует, что . Исходя из определения О-асимптотики, в качестве констант с и положим и .
При анализе алгоритмов теорема о сумме используется следующим образом. Пусть имеются два фрагмента программы P2 и P2, причем время выполнения одного , а другого . Очевидно, что если эти фрагменты выполняются последовательно, то общее время работы (общая трудоемкость последовательно выполняемых фрагментов) будет равно . Тогда асимптотическая оценка всего фрагмента по теореме о сумме – . Это означает, что общая эффективность алгоритма зависит от той части, для которой функция роста трудоемкости имеет наибольший порядок роста, т.е. от наименее эффективной его части алгоритма:
.
Правило произведений.Если T1(n) и Т2(п) имеют степени роста O(f1(n))и O(f2(n))соответственно, то произведение T1(n)T2(n)имеет степень роста O(f1(n) f2(n)).
Доказательство аналогично доказательству правило сумм.
Следствие правила произведений. O(cf(n))эквивалентно О(f(п )), где с — положительная константа. Иными словами положительную константу можно вносить и выносить из-под асимптотической функции.
Например, О(2п2) эквивалентно О(п2).
Дата добавления: 2022-02-05; просмотров: 275;