Практикум №13. АтСД. Оцінка складності алгоритмів PDF

Відокремлений структурний підрозділ «Новокаховський політехнічний фаховий коледж Національного університету «Одеська політехніка» Лабораторна робота - практикум на тему: “ Оцінка складності алгоритмів” © СТАНІСЛАВ МАРУЛІН ...

Відокремлений структурний підрозділ «Новокаховський політехнічний фаховий коледж Національного університету «Одеська політехніка» Лабораторна робота - практикум на тему: “ Оцінка складності алгоритмів” © СТАНІСЛАВ МАРУЛІН  [email protected] ||2 ЗМІСТ 1 Теоретична опис............................................................................. 3 2. Завдання для виконання............................................................. 3 3 Форма подання звіту з лабораторної роботи............................ 10 4 Шкала оцінювання....................................................................... 11 5 Список джерел інформації..... Error! Bookmark not defined.  [email protected] ||3 1 Теоретична опис Складність алгоритму Оцінка складності алгоритмів є важливим етапом при розробці програм і є метрикою яка дозволяє зрозуміти, як змінюється час виконання алгоритму або використання пам'яті при збільшенні розміру вхідних даних. Типи складності: 1. Часова складність (Time Complexity). Визначає, як змінюється час виконання алгоритму при збільшенні розміру вхідних даних. 2. Просторова складність (Space Complexity): Визначає, скільки пам'яті алгоритм використовує для виконання залежно від розміру вхідних даних. Оцінка складності в асимптотичній нотації Асимптотична нотація дає змогу оцінити ефективність алгоритму в залежності від його розміру. Асимптота кривої (грец. ασυμπτωτος — що не збігається, не дотикається) — пряма, до якої крива при віддаленні в нескінченність наближається як завгодно близько.  [email protected] ||4 Найпоширеніші типи асимптотичних оцінок: 1. O(1) — Постійна складність. Час виконання або використана пам'ять не залежить від розміру вхідних даних. Приклад: доступ до елементів масиву за індексом. 2. O(log n) — Логарифмічна складність. Час виконання зростає логарифмічно відносно розміру вхідних даних. Приклад: бінарний пошук. 3. O(n) — Лінійна складність. Час виконання прямо пропорційний розміру вхідних даних. Приклад: обхід списку або масиву. 4. O(n log n) — Лінійно-логарифмічна складність. Зазвичай зустрічається в ефективних сортуваннях, таких як Merge Sort. Приклад: сортування злиттям (Merge Sort). 5. O(n^2) — Квадратична складність. Час виконання зростає квадратично відносно розміру вхідних даних. Часто виникає в алгоритмах з вкладеними циклами. Приклад: сортування бульбашкою (Bubble Sort). 6. O(n^3) — Кубічна складність. Зростає кубічно, часто зустрічається в задачах, де є тройні цикли. Приклад: алгоритми для обробки матриць. 7. O(2^n) — Експоненціальна складність: Час виконання зростає дуже швидко зі збільшенням розміру вхідних даних. Приклад: обчислення всіх можливих підмножин, задача про рюкзак (без динамічного програмування). 8. O(n!) — Факториальна складність. Час виконання зростає дуже швидко, зустрічається в задачах, що потребують генерації всіх перестановок елементів. Приклад: задача про перестановки (перевірка всіх можливих перестановок).  [email protected] ||5 Як оцінювати складність алгоритму Оцінка складності алгоритму здійснюється на основі аналізу його кроків та операцій: 1. Оцінка складності циклів:  Якщо алгоритм містить один цикл, що перебирає всі елементи масиву розміру n, його складність буде O(n).  Якщо алгоритм містить вкладені цикли, кожен з яких перебирає всі елементи, складність буде O(n^2) для двох вкладених циклів, O(n^3) для трьох вкладених циклів і так далі. 2. Оцінка складності рекурсії:  Для рекурсивних алгоритмів складність визначається за допомогою рекурентних співвідношень. Наприклад, у випадку бінарного пошуку складність буде O(log n), а для рекурсивних сортувань, таких як Merge Sort складність буде O(n log n). 3. Оцінка складності пошуку та сортування:  Для пошуку елементу в масиві складність лінійного пошуку буде O(n), а для бінарного пошуку O(log n).  Для сортування масиву швидким сортуванням складність буде O(n log n) в середньому випадку, а в найгіршому випадку — O(n^2).  [email protected] ||6 Приклад оцінки складності Приклад 1: Алгоритм для перевірки парності числа number % 2 == 0 Аналіз складності: Оскільки операція взяття залишку від ділення та перевірка умови займає сталий час, складність цього алгоритму — O(1). Приклад 2: Лінійний пошук у масиві for i in range(len(arr)): if arr[i] == target: return i return -1 Аналіз складності: Алгоритм перебирає всі елементи масиву до того, як знайде цільовий елемент або дійде до кінця. Якщо масив містить n елементів, складність — O(n). Висновки: 1. O(1) — найшвидший тип складності, що вказує на сталий час виконання. 2. O(n) — лінійна складність, вказує на пропорційну залежність часу від розміру вхідних даних. 3. O(n log n) — оптимальна складність для більшості алгоритмів сортування. 4. O(n^2) і вищі — використовуються для менш ефективних алгоритмів, часто з подвійними або трійними вкладеними циклами. 5. O(2^n) і O(n!) — складні алгоритми, що не підходять для великих даних через стрімке зростання часу виконання.  [email protected] ||7 Приклад. Блок-схема для лінійного пошуку в масиві. 1. Початок. Початок алгоритму. 2. Ініціалізація змінної індексу (i = 0). Починаємо пошук з першого елемента масиву. 3. Перевірка умови (i < n). Перевіряємо, чи не вийшли ми за межі масиву. Якщо індекс iii менший за кількість елементів у масиві, продовжуємо. 4. Порівняння (data[i] == item). Порівнюємо поточний елемент з шуканим. Якщо вони рівні, переходимо до наступного кроку. 5. Знайдений елемент (повернути i). Якщо елемент знайдений, повертаємо його індекс. 6. Збільшити i (i = i + 1): Якщо елемент не знайдений, збільшуємо індекс і перевіряємо наступний елемент. 7. Кінець (повернути -1). Якщо елемент не знайдений після проходження всіх guru99.com елементів, повертаємо значення -1. Вхідні дані: масив з N елементів. Часова складність. Оскільки алгоритм перебирає всі елементи масиву в найгіршому випадку (коли елемент знаходиться в кінці масиву або його немає в масиві), часова складність цього алгоритму буде O(n), де N — кількість елементів у масиві. Просторова складність. Оскільки алгоритм використовує лише кілька змінних (індекс і значення, до яких він звертається), просторова складність буде O(1).  [email protected] ||8 2. Завдання для виконання. Визначити часову складність двох задач. Поясніть ваше рішення. 1. Пошук книги. Уявімо, що ви шукаєте конкретну книгу в бібліотеці, де всі книги розташовані в порядку випадковому (не за алфавітом, не за жанрами, просто випадковий порядок). Опис задачі:  Ви заходите в бібліотеку і маєте знайти книгу, яку хочете прочитати.  Крок за кроком ви перевіряєте кожну книгу на полицях.  Коли ви знаходите потрібну книгу — ви припиняєте пошук.  [email protected] ||9 2. Пошук всіх можливих пар шкарпеток однакових кольорів у великій коробці. Уявімо, що у вас є коробка з 𝑛 пар шкарпеток, і ви хочете знайти всі можливі пари шкарпеток однакових кольорів. Кожна пара має один колір, і шкарпетки випадково змішані в коробці. Опис задач і:  У коробці є 𝑛 шкарпеток, і ви хочете знайти всі пари шкарпеток однакового кольору.  Для кожної шкарпетки ви перевіряєте всі інші шкарпетки, щоб знайти пару того ж кольору.  Кожен раз, коли ви знаходите пару шкарпеток однакового кольору, ви записуєте її. Алгоритм:  Перша шкарпетка перевіряється з усіма іншими шкарпетками.  Друга шкарпетка перевіряється з усіма наступними.  Це триває, поки ви не перевірите всі можливі пари шкарпеток.  [email protected] ||10 3 Форма подання звіту з лабораторної роботи 1. Файл в форматі *.pdf або *.doc або *.docx 2. Назва файлу складається з прізвища і назви лр, наприклад: "Марулін. ЛР1. Опис задачі для програмування.". 3. Головне в звіті зазначати суть виконуваного завдання в зручному для Вас вигляді і за допомогою зручних для Вас засобів.  stan 4 Шкала оцінювання Бали за оцінювання самостійної роботи студента (СРС) включені до о лабораторної роботи, а підготовка до лабораторної роботи, включно з вивчен видом самостійної роботи. В таблиці 4.1 зазначена національна шкала оцінювання, шкала ECTS, 100 відповідний переклад з однієї шкали в іншу. Таблиця 4.1 - Таблиця переведення з 12-бальної системи оцінювання інтегрованих загальноосвітн бальної кредитно 12-бальна 100-бальна Оцінка за національною шкалою Шкала шкала кредитно модульна для екзамену, курсового проекту ECTS д оцінювання шкала (роботи), практики 12 100 11 95 А відмінно 90-100 10 90 9 86 В 8 80 80-89 добре за С 7 75 70-79 D 6 69 66-69 задовільно 5 65 E 4 60 60–65 3 45 незадовільно з можливістю не зарахов 2 40 повторного складання повторн FX не зарахова незадовільно з обов`язковим 1 15 повторн повторним вивченням дисципліни ди