Головна

Додавання і множення в O-символіці

  1.  Абсолютна, відносна, переносний рух матеріальної точки. Додавання швидкостей і прискорень.
  2.  Завдання 1. Виконання команди додавання.
  3.  Завдання 2. Виконання команди множення.
  4.  Лабораторна робота №10. множення матриць
  5.  Логічні операції (додавання, множення, заперечення)
  6.  Матриці, складання, віднімання, множення
  7.  Методика 7.1. Додавання чисел з перемиканням

Правило суми. якщо и  , то  . (Аналогічні твердження справедливі також для множин и  ).

Доведення. (Доказ цієї теореми грунтується простому співвідношенні для довільних дійсних чисел , , ,  : якщо и  , то )

оскільки  , Існує константа с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).




 Міністерство освіти Російської Федерації |  Поняття алгоритму та структури даних |  Поняття складності та ефективності алгоритмів і структур даних |  Асимптотично точна оцінка функції зростання |  Основні класи ефективності |  Принципи аналізу ефективності нерекурсивних алгоритмів |  Приклади аналізу алогрітмов |  Формули, що використовуються при аналізі алгоритмів |  Правила роботи з сумами |

© 2016-2022  um.co.ua - учбові матеріали та реферати