загрузка...
загрузка...
На головну

Асимптотический аналіз алгоритмів

  1. HANSEI REPORT (АНАЛІЗ)
  2. I. Аналіз завдання
  3. I. Аналіз інженерно-геологічних умов території, оцінка перспективності її забудови
  4. I. Аналіз інженерно-геологічних умов території, оцінка перспективності її забудови
  5. I. Завдання на аналіз тексту нормативного акта
  6. I. Основні лінії зв'язку педагогіки з соціологією. Мікро- та макроанализ 1 сторінка
  7. I. Основні лінії зв'язку педагогіки з соціологією. Мікро- та макроанализ 2 сторінка

Одним з спрощених видів аналізу, що використовуються на практиці, є асимптотический аналіз алгоритмів. Метою асимптотичного аналізу є порівняння витрат часу та інших ресурсів різними алгоритмами, призначеними для вирішення однієї і тієї ж задачі, при великих обсягах вхідних даних.

При аналізі поведінки функції трудомісткості алгоритму часто використовують прийняті в математиці асимптотические позначення, що дозволяють показати швидкість росту функції, маскуючи при цьому конкретні коефіцієнти.

Така оцінка функції трудомісткості алгоритму називається складністю алгоритму і дозволяє визначити переваги у використанні того чи іншого алгоритму для більших значень розмірності вихідних даних.

У асимптотичному аналізі прийняті наступні позначення:

1. оцінка ? (тетта)

Нехай f (n) і g (n) - позитивні функції позитивний аргумент, n> = 1 (кількість об'єктів на вході і кількість операцій позитивними числа), тоді:

f (n) = ? (g (n)), якщо існують позитивні c1, з2, n0, Такі, що: cl · G (n) = 2 * G (n), при n> n0

Зазвичай кажуть, що при цьому функція g (n) є асимптотично точною оцінкою функції f (n), т. К. За визначенням функція f (n) не відрізняється від функції g (n) з точністю до постійного множника.

Відзначимо, що з f (n) = ? (g (n)) слід, що g (n) = ? (f (n)). приклади:

1) f (n) = 4n2+ NlnN + 174 - f (n) = ?(n2);

2) f (n) = ? (l) - запис означає, що f (n) або дорівнює константі, не дорівнює нулю, або f (n) обмежена константою на ?: f (n) = 7 + 1 / n = ? (1 ).

2. Оцінка О (О велике)

На відміну від оцінки ?, оцінка Про вимагає тільки, що б функція f (n) не перевищувала g (n) починаючи з n> n0, З точністю до постійного множника:

Взагалі, запис O (g (n)) позначає клас функцій, таких, що всі вони ростуть не швидше, ніж функція g (n) з точністю до постійного множника, тому іноді говорять, що g (n) мажорірует функцію f (n) .

Наприклад, для всіх функцій:

f (n) = l / n, f (n) = 12, f (n) = 3 · n + 17, f (n) = n · Ln (n), f (n) = 6 · n2+ 24 · п + 77 буде справедлива оцінка про (n2)

Вказуючи оцінку О, є сенс вказувати найбільш «близьку» мажорірующую функцію, оскільки наприклад для f (n) = n2 справедлива оцінка про (n2), Проте вона не має практичного сенсу.

3. Оцінка ? (Омега)

На відміну від оцінки О, оцінка ? є оцінкою знизу, т. Е. Визначає клас функцій, які ростуть не повільніше, ніж g (n) з точністю до постійного множника:

Наприклад, запис ? (N · Ln (n)) позначає клас функцій, які ростуть не повільніше, ніж g (n) = n · Ln (n), в цей клас потрапляють всі поліноми зі ступенем більшої одиниці, так само як і всі статечні функції з повним правом великим одиниці.

Асимптотичне позначення Про сходить до підручника Бахмана по теорії простих чисел (Bachman, 1892), позначення ?, ?введени Д. Кнутом (Donald Knuth).

Відзначимо, що не завжди для пари функцій справедливо одне з асимптотичних співвідношень, наприклад для f (n) = n1+sin(n) і g (n) = n не виконується жодна з асимптотичних співвідношень.

У асимптотичному аналізі алгоритмів розроблені спеціальні методи отримання асимптотичних оцінок, особливо для класу рекурсивних алгоритмів. Очевидно, що ? оцінка є більш кращою, ніж оцінка О. Знання асимптотики поведінки функції трудомісткості алгоритму - його складності, дає можливість робити прогнози щодо вибору більш раціонального з точки зору трудомісткості алгоритму для великих розмірностей вихідних даних.

Зокрема, проблема зупинки також є частково розв'язати проблемою, а проблеми еквівалентності і тотальності не є такими.

Контрольні питання

1. Що являє собою рішення задачі на ПЕОМ?

2. Охарактеризуйте етапи рішення задачі на ПЕОМ.

3. Що таке алгоритм?

4. Назвіть основні властивості алгоритмів і дайте їм характеристику.

5. Опишіть способи запису алгоритмів.

6. Що таке псевдокод?

7. Дайте перелік блоків в методі блок-схем.

8. Дати поняття «структура даних».

9. Привести класифікацію структур даних.

10. Що називається структурою зберігання?

11. Чим відрізняються фізичні і логічні структури даних?

12. Яка ознака структури даних є найбільш важливим?

13. Дати визначення типу даних.

14. Які бувають типи даних? Охарактеризуйте їх.

15. На які обчислювальні процеси діляться алгоритми? Привести приклади основних обчислювальних процесів (алгоритмів).

16. Які процеси мають місце при обчисленні арифметичних виразів?

17. Що є метою аналізу трудомісткості алгоритмів?

18. Дайте визначення «трудомісткість» алгоритму і «функція трудомісткості».

19. Як проводиться аналіз алгоритмів?

20. Що є метою асимптотичного аналізу алгоритмів?





Ці два різновиди пам'яті розрізняються швидкодією і питомоющільністю (ємністю зберігається). | Накопичувачі на магнітних дисках. | Накопичувачі на оптичних дисках | Флеш-пам'ять | Стратегія вирішення завдань. | Алгоритми (властивості, реалізація алгоритмів) | структури даних | Складові (складні). | Основні обчислювальні алгоритми. | Порівняльні оцінки алгоритмів |

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