Недоліки визначення складності алгоритмів за допомогою О-оцінок

До основних недоліків визначення складності алгоритмів можна віднести наступні:

1. для складних алгоритмів отримання O-оцінок, як правило, або дуже трудомістко, або практично неможливо,

2. часто важко визначити складність "в середньому",

3. O-оцінки занадто грубі для відображення більш тонких відмінностей алгоритмів,

4. O-аналіз дає занадто мало інформації (або зовсім її не дає) для аналізу поведінки алгоритмів при обробці невеликих обсягів даних.

 

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

Ще одна складність - визначення "середнього випадку". Зазвичай зробити це досить важко через неможливість передбачення умов роботи алгоритму. Іноді алгоритм використовується як фрагмент великої, складної програми. Іноді ефективність роботи апаратури та / або операційної системи, або деякої компоненти компілятора істотно впливає на складність алгоритму. Часто один і той же алгоритм може використовуватися в безлічі різних додатків.

Через труднощі, пов'язані із проведенням аналізу часової складності алгоритму "в середньому", часто доводиться задовольнятися оцінками для гіршого і кращого випадків. Ці оцінки по суті визначають нижню та верхню межі складності "в середньому".

Можливо, основним недоліком O-функцій є їх грубість. Якщо алгоритм А виконує певну задачу за 0.001*N сек, в той час як для її ж рішення за допомогою алгоритму В потрібно 1000*N сек, то В в мільйон разів швидше, ніж А. Проте А і В мають одну і ту ж часову складність O(N).

Існують ще й інші форми складності, про які не слід забувати: просторова і інтелектуальна складність.

Про просторову складність як обсяг пам'яті, необхідний для виконання програми, вже згадувалося раніше.

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

Всі три форми складності звичайно взаємопов'язані. Як правило, при розробці алгоритму з хорошою часової оцінкою складності доводиться жертвувати його просторовою та / або інтелектуальною складністю. Наприклад, алгоритм швидкого сортування істотно швидше, ніж алгоритм сортування вибірками. Плата за збільшення швидкості сортування виражена в більшому обсязі необхідної для сортування пам'яті. Необхідність додаткової пам'яті для швидкого сортування пов'язана з багаторазовими рекурсивними викликами.

Алгоритм швидкого сортування характеризується також і більшої інтелектуальної складністю в порівнянні з алгоритмом сортування вставками. Якщо запропонувати сотні людей відсортувати послідовність об'єктів, то найімовірніше, більшість з них використовують алгоритм сортування вибірками. Малоймовірно також, що хтось із них скористається швидким сортуванням. Причини великої інтелектуальної та просторової складності швидкого сортування очевидні: алгоритм рекурсивний, його досить важко описати, алгоритм довший (мається на увазі текст програми), чим більш прості алгоритми сортування.

 

Сортування.

Сортування - процес перестановки елементів списків в певному порядку.

Методи сортування:

1. бульбашкове;

2. вибіркою;

3. вставкою;

4. інші методи

 

Бульбашкове сортування.

При обмінному сортуванні впорядкований список В’ виходить з В систематичним обміном пари елементів, що стоять поруч та не відповідають необхідному порядку, доки такі пари існують.

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

 

Приклад.

B = <20, -5,10,8,7>, вихідний список;

B1 = <-5,10,8,7,20>, перший перегляд;

B2 = <-5,8,7,10,20>, другий перегляд;

B3 = <-5,7,8,10,20>, третій перегляд.

 

Сортування вибіркою.

Упорядкований список В' виходить з В багаторазовим застосуванням вибірки з В мінімального елемента, видаленням цього елементу з В і додаванням його в кінець списку В', який спочатку повинен бути порожнім.

 

Приклад.

B=<20,10,8,-5,7>, B'=<>

B=<20,10,8,7>, B'=<-5>

B=<20,10,8>, B'=<-5,7>

B=<20,10>, B'=<-5,7,8>

B=<20>, B'=<-5,7,8,10>

B=<>, B'=<-5,7,8,10,20>.

 

Сортування вставкою.

Упорядкований масив B' виходить з В у такий спосіб: спочатку він складається з одного елемента К1; далі для i=2,...,N виконується вставка вузла Кi в B' так, що B' залишається впорядкованим списком довжини i.

 

Приклад.

Для початкового списку B = <20, -5,10,8,7> маємо:

B=<20,-5,10,8,7> B'=<>

B=<-5,10,8,7> B'=<20>

B=<10,8,7> B'=<-5,20>

B=<8,7> B'=<-5,10,20>

B=<7> B'=<-5,8,10,20>

B=<> B'=<-5,7,8,10,20>

 

Завдання для виконання лабораторної роботи №4.

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

Варіанти завдань:

1. Отсортувати циклічний список, що містить цілі числа, методом бульбашкового сортування.

2. Отсортувати двонаправлений список, що містить цілі числа, методом бульбашкового сортування.

3. Отсортувати циклічний список, що містить рядки, методом бульбашкового сортування.

4. Отсортувати двонаправлений список, що містить рядки, методом бульбашкового сортування.

5. Отсортувати циклічний список, що містить цілі числа, методом вставки.

6. Отсортувати двонаправлений список, що містить цілі числа, методом вставки.

7. Отсортувати циклічний список, що містить рядки, методом вставки.

8. Отсортувати двонаправлений список, що містить рядки, методом вставки.

9. Отсортувати циклічний список, що містить цілі числа, за допомогою вибору.

10. Отсортувати двонаправлений список, що містить цілі числа, за допомогою вибору.

11. Отсортувати циклічний список, що містить рядки, за допомогою вибору.

12. Отсортувати двонаправлений список, що містить рядки, за допомогою вибор.

 

Вимоги до звіту:

 

Звіт з лабораторної роботи повинен відповідати наступній структурі:

1. Словесна постановка задачі. У цьому підрозділі проводиться повний опис завдання. Описується суть завдання, аналіз вхідних в неї фізичних величин, район їх допустимих значень, одиниці їх вимірювання, можливі обмеження, аналіз умов при яких завдання має рішення (не має рішення), аналіз очікуваних результатів.

2. Математична модель. У цьому підрозділі вводяться математичні описи фізичних величин і математичний опис їх взаємодій. Мета підрозділу - представити вирішувану задачу в математичній формулюванні.

3. Алгоритм рішення задачі. У підрозділі описується розробка структури алгоритму, обгрунтовується абстракція даних, завдання розбивається на підзадачі. Приводится схема алгоритму або псевдокод. Вказується оцінка алгоритму.

4. Лістинг програми.

5. Контрольний тест. Підрозділ містить набори вихідних даних і отримані в ході виконання програми результати.

6. Висновки з лабораторної роботи.

Лабораторна робота №5

 

Тема: Реалізація й обхід дерев.

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

 

Поняття “дерево”.

Дерево - це сукупність елементів, які називаються вузлами (один з яких визначено як корінь), і відносин («батьківських»), що утворюють ієрархічну структуру вузлів. Вузли, так само, як і елементи списків, можуть бути елементами будь-якого типу. Ми будемо зображати вузли буквами, рядками або числами. Формально дерево можна рекурентно визначити наступним чином.

1. Один вузол є деревом. Цей же вузол також є коренем цього дерева.

2. Нехай - це вузол, а - дерева з корінням відповідно. Можна побудувати нове дерево, зробивши батьком вузлів . У цьому дереві буде коренем, а - піддеревом цього кореня. Вузли називаються синами вузла .

 

Графічне подання дерев.

Варіанти подання дерев:

1. с допомогою списку синів;

2. с допомогою покажчиків.