Алгоритми: Складність та Big O

Алгоритми

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

Складність алгоритму та Big O

• Складність алгоритму є оцінкою обсягу роботи, необхідної для виконання цього алгоритму, що використовується для порівняння з іншими алгоритмами, які досягають того ж результату.
• Два ключові фактори, які використовуються для порівняння у програмуванні: час та пам'ять.
• Складність залежить від вхідних даних; обробка списку з 10 клієнтів вимагає менше часу та пам'яті, ніж аналогічна обробка списку з 100 000 клієнтів.
• Найважливішим є те, як збільшення обсягу вхідних даних впливає на використання ресурсів, зокрема часу та пам'яті.

Big O

• Кількість вхідних даних позначається літерою n.
• Оцінюється функція зміни кількості операцій, які виконає алгоритм, в залежності від кількості вхідних даних n.
• «Big O»(O-нотація) - це поняття, яке допомагає відстежувати зростання та порівнювати затрати ресурсів.
• Big O є описом верхньої можливої межі.
• TC(Time Complexity) або Час - це час, який вимірює складність.
• Наприклад, алгоритм друку всіх значень масиву int, що має N елементів, має складність алгоритму O(N), оскільки потрібно перевірити кожен елемент масиву.

Обчислення складності алгоритму

• Кількість елементів масиву відповідає кількості ітерацій у циклі.
• Для масиву з 10 елементами потрібно 10 ітерацій, для 100 000 - 100 000.
• У прикладі, де потрібно друкувати елементи масиву, поки не зустрінеться цільове значення(goal), складність не перевищить O(N).

Пам'ять (Space Complexity, чи SC)

• Хороший програміст повинен піклуватися про обсяг витраченої пам'яті чи простору.
• Просторова складність є паралельним поняттям часової складності.
• З одного боку верхня межа часу — TC.
• З іншого — верхня межа простору SC.
• Слід думати про часову(TC) та просторову(SC) складності одночасно.

TC та SC

• Іноді потрібно знехтувати одним показником заради іншого.
• Алгоритм, що "бігає" по вхідному масиву має O(1) SC.
• O(1) використовується для опису константної складності алгоритму.
• У прикладі, коли створюється новий масив, такого ж розміру, як і вхідний, та копіюються всі дані, ТС — O(N), SC стало O(N), а було О(1).

O(1) — Константна складність (Constant)

• Алгоритм має О(1) складність, коли відомо скільки точно разів щось відбудеться, чи скільки пам'яті буде виділено, незалежно від зміни вхідних даних.
• Алгоритм завжди використовуватиме однакову кількість ресурсів, досягнення якої слід прагнути.
• Наприклад: алгоритм друку чисел від 1 до 100 має TC і SC — O(1), оскільки точно відомо скільки потрібно ітерацій(100) та Скільки пам'яті буде виділено.

Кількість пам'яті

• У C++ int змінна займає 4 байти, у прикладі 2 змінні (n та i), які потребують 4+4=8 байтів.
• Знаючи точну кількість, виділеної пам'яті, можна сказати О(1) SC.
• Доступ до будь-якого елементу масиву має О(1) складність.
• O(N), про який піде мова далі у розділі, швидше ніж О(1).

O(N) — Лінійна складність (Linear)

• ТС — кількість ітерацій = кількості елементів.
• SC - якщо потрібно створити масив з N елементів, це буде O(N) SC.

O(log N) — Логарифмічна складність (Logarithmic)

• O(log N) є однією з найважливіших, оскільки багато алгоритмів мають таку складність.
• Це алгоритм, у якому на кожному етапі кількість елементів зменшується вдвічі.
• Потрібно лише 9 ітерацій для O(log N) замість 1000 ітерацій для O(N), коли маємо 1000 елементів масиву.
• У математиці, логарифм використовується для вираження кількості разів, скільки потрібно помножити одне число, щоб отримати інше.

Багатокомпонентні алгоритми

• Якщо алгоритм складається з декількох кроків, для визначення складності потрібно розглядати їхню сукупність.
• Загальна складність O(N+N) = O(2N), скорочується до O(N), оскільки константи не враховуємо.

Додавання

• Складність O(N²) + O(N) спрощується до O(N²), оскільки O(N) не є домінуючою умовою зростання.
• Формула діє лише для одного набору вхідних даних.

Множення

• TC для вкладених циклів обчислюється шляхом множення складностей кожного циклу.
• ТС для двох вкладених циклів, кожен з яких має складність O(N), становить O(N*N) = O(N²).

Складні випадки

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

O(N²) — Квадратична складність (Quadratic)

• У випадку вхідного масиву з 5 елементів кількість ітерацій становить 25(5*5).
• Поширена складність для алгоритмів сортування та операцій над двовимірними масивами.

O(NlogN) — Лінійно-логарифмічна складність(Linearithmic)

• Повільніша за лінійну складність, але значно швидша за квадратичну.
• Лінійно-логарифмічну складність застосовують в ефективних алгоритмах сортування(merge sort, quicksort).

O(2") — Експоненціальна складність (Exponential)

• Алгоритми з такою складністю часто зустрічаються у рекурсії і динамічному програмуванні.

O(N!) — Факторіальна складність (Factorial)

• Дуже швидко зростаюча складність, що може виникнути при перестановці елементів у рядку всіма можливими способами.
• Рекомендовано завжди намагатися використовувати алгоритми зі швидшою складністю, проте бувають специфічні випадки, коли без алгоритмів з O(N!) не обійтись.

Структури даних

• Структура даних - це спосіб організації та зберігання даних в комп'ютері, який дозволяє ефективно отримувати до них доступ та змінювати.

Масив

• Масив - це скінченний набір елементів одного типу, які зберігаються в послідовних комірках пам'яті.
• Розташування елементів масиву в пам'яті послідовне, що дозволяє отримувати доступ до будь-якого елемента масиву за O(1).
• Для вставки або видалення елемента з масиву потрібно створити новий масив, більшого розміру, та перенести всі значення зі старого, що займає O(N).
• Доступ до комірки масиву здійснюється за індексом, шляхом додавання індексу до адреси початку масиву.

Зв'язний список (Linked List)

• Зв'язний список - це структура даних, яка є послідовністю вузлів, де кожен вузол містить дані і вказівник на наступний вузол(або на попередній та наступний, у випадку двозв'язного списку).
• Вузли можуть бути розташовані в пам'яті хаотично.
• Доступ до конкретного вузла вимагає перевірки послідовно один за одним, що займає O(N).
• Вставку/видалення вузла з початку або кінця списку можна виконати за O(1).

Стек

• Стек працює за принципом LIFO(Last-In-First-Out), коли останній прийшов — перший вийшов.
• Не використовується для доступу до елементів всередині стеку(O(N)).
• Стеки цінуються за O(1), коли потрібно додати, прочитати, видалити останній, перевірити, чи не порожній стек.

Класичні функції стеку

• push(something): додати новий елемент.
• top(): прочитати останній елемент.
• empty(): перевірити, чи порожній стек.
• pop(): видалити останній елемент.

Черга

• Черга(Queue) працює за принципом FIFO (First-In-First-Out), тобто перший прийшов - перший вийшов.
• Рекомендовано до використання, коли необхідно зчитати/видалити перший елемент, додати новий елемент в кінець, перевірити стан черги. Всі ці маніпуляції мають складність O(1).

Класичні функції черги

• push(): додати новий елемент в кінець черги.
• pop(): видалити елемент з початку черги.
• front(): прочитати елемент з початку черги.
• empty(): перевірити, чи порожня черга.

Дерево

• Дерево складається з вузлів і ребер, які їх зв'язують.
• Кожне дерево починається з кореневого вузла(root node), який має дочірні(child nodes).
• Дочірні вузли своєю чергою, дочірні вузли можуть мати свої дочірні вузли, і так далі.
• Вузол вважається батьківським для своїх дочірніх.
• Кореневий вузол є батьківським для всіх вузлів дерева.
• Листовий вузол(leaf node) — не має дочірніх вузлів.
• Висота дерева(height) — максимальна кількість ребер від кореневого до листового вузлів.
• Глибина дерева кількість ребер від вузла до кореневого вузла.

Бінарне дерево (Binary Tree)

• Є дерево, в якому кожен вузол має не більше двох дочірніх.

Бінарне дерево пошуку (Binary Search Tree або BST)

• Бінарне дерево, в якому значення лівого дочірнього вузла менше або дорівнює значенню батьківського, а значення правого дочірнього вузла більше N ( значення ) <.

Збалансоване та незбалансоване дерево

• Збалансованим є дерево, у якого глибина всіх листових вузлів відрізняється не більше ніж на 1.
• Якщо дерево має лише один дочірній вузол, то глибина повинна бути не більшою за 1.

Закінчене бінарне дерево (Complete Binary Tree)

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

Повне бінарне дерево (Full Binary Tree)

• Дерево, у якого кожен вузол має нуль або два дочірні вузли.

Ідеальне бінарне дерево (Perfect Binary Tree)

• Є дерево, яке є закінченим і повним одночасно.
• Всі листові вузли знаходяться на одному рівні, який заповнений максимально можливою кількістю вузлів.

Обхід бінарного дерева(Binary Tree Traversal)

• При роботі з деревами часто застосовують рекурсію.

Види обходу бінарного дерева

• In-Order Traversal: дійти до крайнього лівого вузла, зробити дію з даними, піти вправо.
• Pre-Order Traversal: зробити дію з даними, піти вліво, потім вправо.
• Post-Order Traversal: дійти до крайнього лівого вузла, піти вправо, зробити якусь дію з даними.

Хеш-таблиця (Hash Table)

• Структура даних, яка зіставляє ключі зі значеннями для високоефективного пошуку.

Реалізації хеш-таблиці

• Масив зв'язних списків та функція гешування.
• Збалансоване дерево бінарного пошуку.

Граф (Graph)

• Колекція вузлів(nodes) та ребер(edges).
• Граф є структурою даних, що дозволяє моделювати зв'язки між об'єктами.

Підвиди графу

• Орієнтований/спрямований(Directed graph).
• Неорієтований/без напрямку(Undirected graph).

Важливі концепти

• Сусід - вузол, який знаходиться поруч та до якого можливо дістатися. Також вузол, куди можна дістатись.
• Список сумісності(Adjacency list) - уявлення графу.
• Breadth first traversal - від початкового вузла перевіряються усі сусіди по черзі, у ширину. Реалізувати даний алгоритм допомагає черга(Queue).
• Depth first traversal - у глибину. Реалізувати даний алгоритм допомагає стек(Stack) або рекурсія.