Лекція. АтСД. Виконавча складність алгоритму PDF

Відокремлений структурний підрозділ «Новокаховський політехнічний фаховий коледж Національного університету «Одеська політехніка» Виконавча складність алгоритмів © Станіслав Марулін  ПЛАН ЛЕКЦІЇ 2 1. Алгори...

Відокремлений структурний підрозділ «Новокаховський політехнічний фаховий коледж Національного університету «Одеська політехніка» Виконавча складність алгоритмів © Станіслав Марулін  ПЛАН ЛЕКЦІЇ 2 1. Алгоритм. 2. Роль алгоритмів в комп’ютерних дисциплінах. 3. Класика. 4. Алгоритми і структури даних. 5. Обчислювальна складність алгоритму – Big O. 6. Складність - O(1). 7. Складність - O(n). 8. Складність - O(n^2). 9. Складність - O(log n).  Алгоритм 3 У математиці та інформатиці алгоритм – кінцева послідовність строгих інструкцій, які використовуються для вирішення певного класу проблем або для виконання обчислень. ↓ Обчислення – будь-який тип арифметичного або неарифметичного обчислення, який є чітко визначеним. Типовими прикладами обчислень є математичні рівняння та комп’ютерні алгоритми. ↓ Computation from the Free Merriam-Webster Dictionary "Computation: Definition and Synonyms from Answers.com". Answers.com. Archived from the original on 22 February 2009. Retrieved 26 April 2017. "Definition of ALGORITHM". Merriam-Webster Online Dictionary. Archived from the original on February 14, 2020. Retrieved November 14, 2019.  Алгоритм 4 Комп’ютерні алгоритми - являють собою набір чітко визначених інструкцій, які використовуються для вирішення конкретної проблеми. Алгоритми формують основу для створення продуктивних і ефективних програм. Computation from the Free Merriam-Webster Dictionary "Computation: Definition and Synonyms from Answers.com". Answers.com. Archived from the original on 22 February 2009. Retrieved 26 April 2017. "Definition of ALGORITHM". Merriam-Webster Online Dictionary. Archived from the original on February 14, 2020. Retrieved November 14, 2019.  Алгоритм 5 Алгоритм в computer science – структурований, однозначний і покроковий набір інструкцій, які використовуються для вирішення проблеми або досягнення певної мети. Computation from the Free Merriam-Webster Dictionary "Computation: Definition and Synonyms from Answers.com". Answers.com. Archived from the original on 22 February 2009. Retrieved 26 April 2017. "Definition of ALGORITHM". Merriam-Webster Online Dictionary. Archived from the original on February 14, 2020. Retrieved November 14, 2019.  Роль алгоритмів в комп’ютерних дисциплінах 6 1. Допомагають зменшити складність проблеми, розбиваючи її на менші, керовані підпроблеми. 2. Необхідні для обробки даних і забезпечення ефективного використання пам’яті. 3. Забезпечують безпеку та захист даних, особливо в таких сферах, як криптографія. 4. Важливий інструмент для пошуку даних у великих базах даних за допомогою алгоритмів пошуку. Computation from the Free Merriam-Webster Dictionary "Computation: Definition and Synonyms from Answers.com". Answers.com. Archived from the original on 22 February 2009. Retrieved 26 April 2017. "Definition of ALGORITHM". Merriam-Webster Online Dictionary. Archived from the original on February 14, 2020. Retrieved November 14, 2019.  Класика 7 Bubble Sort. Використовується для сортування елементів у певному порядку (за зростанням або спаданням). https://www.softwareideas.net/a/1598/bubble-sort-flowchart- https://www.researchgate.net/figure/Illustration-of-Dijkstras-algorithm_fig1_331484960 https://iq.opengenus.org/euclidean-algorithm-greatest-common-divisor-gcd  Класика 8 Binary Search. Використовується для пошуку елементів у відсортованому списку або масиві. https://www.softwareideas.net/a/1598/bubble-sort-flowchart- https://www.researchgate.net/figure/Illustration-of-Dijkstras-algorithm_fig1_331484960 https://iq.opengenus.org/euclidean-algorithm-greatest-common-divisor-gcd  Класика 9 Dijkstra's Algorithm. Використовується для пошуку найкоротшого шляху між вузлами в гра 7-1 = 6 5 6 7 Б 5 В 1 О 14-7 = 7 6-4 = 2 14 0 10 А 3 Д 8 К 2-2 =0 Ж 2 З 3 І 2 4 7 https://www.softwareideas.net/a/1598/bubble-sort-flowchart- https://www.researchgate.net/figure/Illustration-of-Dijkstras-algorithm_fig1_331484960 https://iq.opengenus.org/euclidean-algorithm-greatest-common-divisor-gcd  Класика 10 Euclidean Algorithm. Використовується для знаходження найбільшого спільного дільника двох чисел. https://www.softwareideas.net/a/1598/bubble-sort-flowchart- https://www.researchgate.net/figure/Illustration-of-Dijkstras-algorithm_fig1_331484960 https://iq.opengenus.org/euclidean-algorithm-greatest-common-divisor-gcd  Алгоритми і структури даних 11 Структури даних — спосіб організації та зберігання даних у комп’ютері, щоб їх можна було ефективно використовувати, для виконання операцій вставки, видалення та пошуку, алгоритм —покрокова процедура, призначена для виконання певних операцій. Під час виконання ПЗ, структури даних і алгоритми взаємодіють у фоновому режимі, забезпечуючи оптимальну роботу ПЗ. https://www.studysmarter.co.uk/explanations/computer-science/algorithms-in-computer-science/  Алгоритми і структури даних 12 Алгоритми використовують структури даних для вирішення обчислювальних проблем, і вибір правильної структури даних може значно підвищити ефективність алгоритму. https://www.studysmarter.co.uk/explanations/computer-science/algorithms-in-computer-science/  Алгоритми і структури даних 13 1. Структури даних дозволяють ефективно маніпулювати даними. 2. Полегшують обчислення, таким чином підвищуючи ефективність алгоритму. 3. Правильно підібрані структури даних можуть зменшити складність програми. 4. Дозволяють ефективно обробляти великі обсяги даних. https://www.studysmarter.co.uk/explanations/computer-science/algorithms-in-computer-science/  Типи структур даних та їх алгоритми 14 Структури даних поділяються на два типи — примітивні та непримітивні. Примітивні структури даних включають базові типи: integer, float, char, boolean. Непримітивні структури даних визначені користувачем типи: Array, Stack, Queue, List, Tree. https://www.studysmarter.co.uk/explanations/computer-science/algorithms-in-computer-science/  Типи структур даних та їх алгоритми 15 Кожна структура даних має пов’язаний набір алгоритмів, які можуть бути виконані над нею: Структура даних Алгоритми Array Search, Sort, Insert, Update, Delete Stack Push, Pop, Peek/Top Queue Enqueue, Dequeue, Front, Rear Tree Pre-order, In-order, Post-order Traversal Breadth-First Search, Depth-First Search, Graph Dijkstra https://www.studysmarter.co.uk/explanations/computer-science/algorithms-in-computer-science/  Обчислювальна складність алгоритму – Big O 16 Вибір структури даних залежить від конкретної задачі: від виду даних та алгоритму їх обробки. Обчислювальна складність поняття в інформатиці та теорії алгоритмів, що позначає функцію залежності обсягу роботи, яка виконується деяким алгоритмом, від розміру вхідних даних – O(f(n)). Знаючи обчислювальну складність алгоритму можна прийняти рішення, яку структуру даних вибрати.  Обчислювальна складність алгоритму – Big O 17 Знаючи алгоритм обробки даних та сам вид подання даних можна зробити висновок про складність алгоритму.  Часова складність та просторова складність 18 Часова складність (Time Complexity) визначає, скільки операцій потрібно виконати для виконання алгоритму, залежно від кількості елементів у колекції (наприклад, масиві з n елементами).  Часова складність та просторова складність 19 Оцінка часової складності здійснюється для трьох випадків: Найгірший випадок (Worst case) - ситуація, коли алгоритм виконується найповільніше. Зазвичай вимірюється для найгірших входів. Worst case для алгоритму лінійного пошуку. X = 10 A 3 1 7 15 -55 4 9 10 0 1 2 3 4 5 6 7  Часова складність та просторова складність 20 Середній випадок (Average case) – середній час роботи алгоритму, коли вхідні дані випадкові або відомі на рівні статистичних характеристик. Середній випадок для лінійного пошуку описує ситуацію, коли шуканий елемент знаходиться не в кінці масиву і не обов'язково є відсутнім. В цьому випадку алгоритм знаходить шуканий елемент в деякому випадковому місці масиву, не перевіряючи усі елементи. X = -55 A 3 1 7 15 -55 4 9 10 0 1 2 3 4 5 6 7  Часова складність та просторова складність 21 Кращий випадок (Best case) – найшвидший варіант, наприклад, коли список уже відсортований. Найкращий випадок для лінійного пошуку описує ситуацію, коли шуканий елемент знаходиться на самому першому місці в колекції. У цьому випадку алгоритм знаходить шуканий елемент вже після першого порівняння, без необхідності перевіряти інші елементи. X=3 A 3 1 7 15 -55 4 9 10 0 1 2 3 4 5 6 7  Часова складність та просторова складність 22 Постійна складність - O(1). Алгоритм виконується за сталий час, незалежно від розміру вхідних даних. Наприклад, доступ до елемента в масиві за індексом. Завдання. Знайти елемент у масиві із заданим номером. int[] array = new int; // великий масив array = 10; // присвоєння значення за індексом int element = array;// доступ до елемента за індексом Складність – кількість операцій, що виконуються для досягнення результату, залежно від введення (операцій на введення). Кількість операцій = 1. Складність - O(1).  Часова складність та просторова складність 23 Лінійна складність - O(n). Час виконання пропорційний розміру вхідних даних (перебір всіх елементів масиву). Завдання. Знайти суму елементів масиву. int [] i = new int[]{1,2,3}; int k = i; int sum = 0; for(int num:i) sum += num; Складність - скільки операцій на введення буде потрібно? Перебрати все елементи, тобто операція на кожен елемент. Чим більший масив, тим більше операцій. Кількість операцій = 3. Складність - O(3). Такий тип алгоритмів називають "лінійними" або що алгоритм "лінійно масштабується".  Часова складність та просторова складність 24 Складність - O(1). Завдання. Знайти суму елементів відсортованого без перепусток масиву, який починається з 1. S = n(n+1)/2 int [] i= new int[]{1,2,3}; int sum = 0; sum = (i[i.length-1]*((i[i.length-1])+1))/2; Складність - скільки операцій на введення буде потрібно? Визначити значення останнього елемента n. Кількість операцій = 1. Складність - O(1).  Часова складність та просторова складність 25 Фактично операцій не одна: - отримати довжину масиву; - отримати останній елемент; - виконати множення та ділення. В O нотації фактична кількість кроків не важливо, важливо, що алгоритм виконується за константний час. Алгоритми із константним часом завжди = O(1). Фактично операцій може бути O(n+10) = O(n).  Часова складність та просторова складність 26 Квадратична складність - O(n^2). Час виконання пропорційний квадрату розміру вхідних даних. Це типовий приклад для алгоритмів з подвійними вкладеними циклами (сортування бульбашкою). Завдання. Перевірити масив на наявність дублів. int [] array = new int[]{1,2,3,4,5,1}; for (int i = 0; i < array.length; i++) { int thisNum = array[i]; //новий цикл по тому ж масиву, O(n^2) for (int j = 0; j < array.length; j++) { if (j != i) { int otherNum = array[j]; if (otherNum == thisNum){ System.out.println("Дублікат є!"); System.exit(0); } } }  Часова складність та просторова складність 27 Складність - скільки операцій на введення буде потрібно? Ітерування масиву - O(n) + вкладений цикл, кожного елемента ми ще раз ітеруємо - (n^2). Алгоритми з вкладеними циклами з тієї ж колекції завжди O(n^2). Кількість операцій = n^2. Складність - O(n^2).  Часова складність та просторова складність 28 Логарифмічна складність - O(log n). Час виконання збільшується логарифмічно. Завдання. Пошук елемент у масиві. Масив відсортований. Алгоритм «бінарний пошук»: ділимо масив на дві половини, відкидаємо не потрібну, що знову ділимо на дві частини і так поки не знайдемо потрібне значення. Кожен крок зменшує кількість елементів, які потрібно перевірити, у два рази. Алгоритм - «розділяй і володарюй» Divide and Conquer. Часова складність та просторова складність 29 у гіршому випадку робимо стільки операцій, скільки разів можемо поділити масив на дві частини.  Часова складність та просторова складність 30 Цей алгоритм ґрунтується на логарифмі. ax=N loga(N)=x Приклад: якщо у нас масив із 5ти елементів, то складність алгоритму: log2(5) = x 2x = 5 -> x = √5 = 2.236 2.236  Часова складність та просторова складність 31 O(n log n) – Лінійно-логарифмічна складність – Алгоритм виконується лінійно з додаванням логарифмічного фактору. Приклад – сортування злиттям (merge sort). O(2^n) – Експоненціальна складність – Час виконання зростає експоненційно. Це типово для алгоритмів, що перебирають усі можливі варіанти, наприклад, у задачах перебору. O(n!) – Факториальна складність – Час виконання зростає факторіально. Це характерно для задач, де потрібно перебирати всі перестановки елементів (наприклад, задача комівояжера). Просторова складність 32  Просторова складність 33 Просторова складність (Space Complexity) визначає, скільки пам'яті або додаткового простору потрібно для виконання алгоритму. У деяких алгоритмах (наприклад, у Merge Sort) потрібно додатково виділяти пам'ять для допоміжних структур даних, тоді як інші алгоритми (наприклад, Bubble Sort) працюють на місці, без необхідності додаткової пам'яті.  Просторова складність 34 Лінійний пошук є алгоритмом, який працює на місці (in-place), тобто він не використовує додаткову пам'ять для зберігання копій елементів або допоміжних структур даних. Алгоритм використовує постійний обсяг пам'яті для кількох змінних (індексу, порівняння, тощо), які потрібні для виконання пошуку. N A 3 1 7 15 -55 4 9 10 0 1 2 3 4 5 6 7