Основні поняття й ознаки теорії складності
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
> f (n) O(h(n)) і (g)n O(h(n)), то ( f g)(n) O(h(n)).
Якщо f (n) O( h(n)) і g(n) O(l(n)), то ( f g)( n) O(h(n)l(n)).
Рефлексивність f(n) O(f(n)).
Транзитивність. Якщо f(n) O(g(n)) і g(n) O(h(n)), то f(n) O(h(n)).
Складність алгоритмів вимірюють кількістю арифметичних операцій (додавань, віднімань, множень і ділень із залишком), необхідних для виконання всіх дій. Однак це визначення не бере до уваги величини чисел, що беруть участь в обчисленнях. Тому, часто беруть до уваги ще й величину чисел, зводячи обчислення до бітових операцій, тобто оцінюючи кількість необхідних операцій із цифрами 0 і 1, у двійковому записі чисел. Це залежить від задачі, що розглядаються.
Даний підхід зручний з таких міркувань. По-перше, у компютерах дані подаються і обробляються у двійковому вигляді, а інші подання в основному використовують під час введення даних і під час виведення результатів. По-друге, перевід числа від однієї основи системи обчислень до іншої виконується швидко і потребує виконання арифметичних операцій (ділення з залишком, множення або додаваня чисел), де довжина запису числа (основу логарифмам не вказуємо, оскільки воно не впливає на вид оцінки складності). Перехід до іншої основи є рідкісною операцією, затратами на її виконання можна знехтувати. Нарешті, бітова оцінка непогано відображує реальну складність операцій, оскільки, як правило, оцінки складності для інших основ систем обчислень призводять лише до змін у константному множнику функції оцінки складності. При оцінці складності обчислювальних задач, звичайно, застосовують методи редукції і піднесення до інших задач з відомими оцінками складності.