 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Сложение и умножение в O-символике
Правило суммы. Если 
и 
, то 
. (Аналогичные утверждения справедливы также для множеств 
и 
).
Доказательство. (Доказательство этой теоремы основывается простом соотношении для произвольных вещественных чисел 
, 
, 
, 
: если 
и 
, то 
)
Поскольку 
, существует константа с 1 и неотрицательное целое число n 1 такие, что для всех 
справедливо 
.
По аналогии, поскольку 
существует константа 
и неотрицательное целое число 
такие, что для всех 
справедливо 
.
Обозначим через 
и рассмотрим случай, когда верны оба неравенства для случая 
. Сложив приведенные выше неравенства, получим
.
Откуда следует, что . Исходя из определения О-асимптотики, в качестве констант с и 
положим 
и 
.
При анализе алгоритмов теорема о сумме используется следующим образом. Пусть имеются два фрагмента программы P 2 и P 2, причем время выполнения одного 
, а другого 
. Очевидно, что если эти фрагменты выполняются последовательно, то общее время работы (общая трудоемкость последовательно выполняемых фрагментов) будет равно 
. Тогда асимптотическая оценка всего фрагмента по теореме о сумме – 
. Это означает, что общая эффективность алгоритма зависит от той части, для которой функция роста трудоемкости имеет наибольший порядок роста, т.е. от наименее эффективной его части алгоритма:
.
Правило произведений. Если T1(n) и Т2(п) имеют степени роста O (f 1(n))и O (f 2(n))соответственно, то произведение T1 (n) T2 (n)имеет степень роста O (f 1(n) f 2(n)).
Доказательство аналогично доказательству правило сумм.
Следствие правила произведений. O (cf(n))эквивалентно О (f (п)), где с — положительная константа. Иными словами положительную константу можно вносить и выносить из-под асимптотической функции.
Например, О( 2 п2) эквивалентно О(п2).
Поиск по сайту: