Головна |
Правило суми. якщо и , то . (Аналогічні твердження справедливі також для множин и ).
Доведення. (Доказ цієї теореми грунтується простому співвідношенні для довільних дійсних чисел , , , : якщо и , то )
оскільки , Існує константа с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).
Міністерство освіти Російської Федерації | Поняття алгоритму та структури даних | Поняття складності та ефективності алгоритмів і структур даних | Асимптотично точна оцінка функції зростання | Основні класи ефективності | Принципи аналізу ефективності нерекурсивних алгоритмів | Приклади аналізу алогрітмов | Формули, що використовуються при аналізі алгоритмів | Правила роботи з сумами |