Як здійснюється пошук на dst-деревах і tst-деревах.

Простий порозрядний пошук основується на використанні дерев цифрового пошуку (digital search trees, DST).

Використання DST-дерев ефективно для дуже великого набору даних з невеликий значеннями ключів, по скільки час пошуку обмежується тільки довгого ключа.

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

Наприклад, багатошляхові дерева - значення ключів зберігаються в зовнішніх вузлах і кожен вузол має R-сcилок (R - це основа системи числення).

Якщо значенням ключа є рядок символів, тоді для порозрядного сортування пошуку даних можна використовувати дерево тренер нього пошуку (ternary search tree, TST- дерево).

TST-дерево - це дерево, кожен вузол якого зберігає один символ і три ссилки (зв'язки), ключам, поточні символи яких менше, рівні і більше символу вузла.

 

 

Для чого необхідно аналізувати алгоритми? Які методи застосовуються для аналізу алгоритмів?

Аналіз алгоритму – це спосіб передбачення потрібних ресурсів для його виконання. (оцінки його ефективності)

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

Методи аналізу:

ü Емпіричний аналіз (експериментальний)

ü Математичний аналіз (аналітичний)

Емпіричний аналіз – обрахування часу виконання шляхом запуску на виконання реалізації алгоритмів.

Математичний аналіз – обрахунок відносного часу виконання алгоритму шляхом побудови математичного виразу.

 

У чому полягає сутність емпіричного аналізу алгоритмів? Які умови його застосування?

Допущення при емпіричному аналізі:

1 категорія

1. Алгоритми реалізовані на одній і тій самій мові програмування.

2. Реалізація алгоритмів здійснювалась з однаковою ретельністю.

3. Виконуваний код (програма) алгоритмів був отриманий з використанням одного і того ж самого середовища програмування.

4. Виконання алгоритмів здійснювалось на обрахунковій машині однієї і тієї ж самої архітектури.

2 категорія

1. Використання реальних даних (точний вимір часу виконання).

2. Використання випадкових даних (гарантія аналізу саме алгоритму, вимір середнього часу виконання).

3. Використанні незвичайних даних (вимір найгіршого випадку).

Розглянемо приклад емпіричного аналізу алгоритмів послідовного та бінарного пошуку:

ü Пошук виконується в масиві цілих значень.

ü Розмірність масиву в діапазоні від 103 до 106.

ü Кількість операцій пошуку елемента в діапазоні від 104 до 107.

ü Набір даних та пошук елементів один і той самий.

ü Масив ініціалізується випадковими значеннями.

 

У чому полягає сутність математичного аналізу? Коли він застосовується?

Математичний аналіз

Застосовується якщо:

1. Відсутня реалізація алгоритму;

2. Необхідно передбачити час виконання алгоритму в новому середовищі.

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

Необхідно виконати один головний, який вказує вплив. Зазвичай він пропорційний величині оброблюваного набору даних, тобто параметр N – це розмірність набору даних.

 

Що розуміється під «рост-функцією»? Які є типи «рост-функцій»?

Залежність часу виконання можна виразити через головний параметр з використанням простих математичних формул, що називаються ріст функціями:

1 – постійний час виконання (майже всі операції виконуються один раз чи декілька).

Наприклад пошук по індексованому ключу.

N – лінійний час виконання (якщо кожен елемент отримує обробку).

Наприклад, послідовний пошук.

logN – логарифмічний час виконання (задача розбивається на набір під задач, зі зменшенням розміру задачі на кожному кроці на деякий постійний коефіцієнт, і вирішення визначається в одній із під задач).

Наприклад бінарний пошук.

NlogN – час виконання, пропорціональне NlogN (задача розбивається на під задачі, вирішення яких після об’єднуються).

Наприклад, низхідне сортування зливанням.

N2 – квадратичний час виконання (коли оброблюються всі пари елементів – подвійні цикли).

Наприклад, сортування алгоритмів вставки в найгіршому випадку.

N3 – кубічний час виконання (потрійні цикли).

Наприклад, сортування двовимірного масиву по значенням однієї строки алгоритмом бульбашки.

2N – експоненціальний час виконання (пряме вирішення завдання).

 

32. Що означає «θ-нотація», «О-нотація» та «Ω-нотація»? Як можна їх зобразити графічно?

 

Як застосовується математичний аналіз для оцінки ефективності алгоритмів?

Операції, їх кількість і час виконання.

Отриманий вираз можна перетворити, виразивши через ріст функції.

Для наближеної оцінки часу виконання алгоритму при великих значень N модна спростити математичний вираз відкинувши доданки «нижчих порядків».

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