Вступ в алгоритми

Алгоритм — це набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій. Набір інструкцій це і є програма, а виконавець — це компʼютер. Програми розробляють програмісти. Алгоритми можуть бути досить простими, складатися з декількох інструкцій та виконуватися дуже швидко. А можуть бути складними, складатися з тисяч інструкцій та виконуватися довго.

У цьому розділі:

Одна задача — багато алгоритмів

У контексті інформатики задача (computational problem) — це формальне математичне визначення проблеми, яку потрібно вирішити за допомогою обчислень. Задача складається з вхідних даних (input) і очікуваного результату (output).

Наприклад, задача сортування полягає в упорядкуванні набору елементів за певним критерієм (наприклад, за зростанням або спаданням):

• Вхідні дані: [5, 2, 9, 1, 6]
• Очікуваний результат: [1, 2, 5, 6, 9] (відсортований список у порядку зростання)

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

Основні алгоритми сортування:

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

Властивості алгоритмів

Алгоритми повинні мати певні властивості, щоб бути коректними та ефективними. Основні з них:

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

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

Масовість — алгоритм має бути застосовним до широкого класу вхідних даних, а не лише до одного конкретного випадку. Приклад: алгоритм сортування має працювати як для списку з 10 елементів, так і для списку зі 100, 1000, мільйону елементів.

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

Ефективність — хороший алгоритм повинен виконувати завдання швидко й використовувати мінімальну кількість ресурсів ( процесорного часу, пам’яті). Приклад: два алгоритми можуть виконувати одну задачу, але один з них має часову складність O(n), а інший O(n²). Очевидно, що перший є більш ефективним при великих обсягах даних.

Визначеність — кожен крок алгоритму має бути чітко сформульованим і не допускати двозначного тлумачення. Приклад: якщо в алгоритмі є команда "Зробити щось хороше", то це не є визначеним кроком, оскільки поняття "хороше" може трактуватися по-різному. Натомість "Додати число 5 до кожного елемента списку" — чітка та визначена команда.

Обчислювальна складність

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

Обчислювальна складність визначає, як змінюється кількість операцій у алгоритмі залежно від розміру вхідних даних. Позначається у вигляді Big O notation:

• O(1) – константний час, незалежно від (наприклад, доступ до елемента масиву за індексом).
• O(log n) – логарифмічна складність (наприклад, бінарний пошук).
• O(n) – лінійна складність (наприклад, лінійний пошук).
• O(n²) – квадратична складність (наприклад, сортування вибором).

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

Просторова складність визначає, скільки додаткової пам'яті споживає алгоритм залежно від розміру вхідних даних. Наприклад:

• Алгоритм, що сортує масив "на місці" без додаткової пам’яті, має O(1) просторову складність.
• Алгоритм, який використовує рекурсію (наприклад, швидке сортування), може мати O(log n) або O(n) просторову складність через стек рекурсивних викликів.

Наприклад, можна характеризувати алгоритми сортування за її обчислювальною та просторовую складністю та кращим застосуванням:

Note G — самий перший алгоритм

Note G (1843 р.) — це комп’ютерний алгоритм, написаний Адою Лавлейс, який був розроблений для обчислення чисел Бернуллі за допомогою гіпотетичної аналітичної машини. Note G загальновизнано вважається першим алгоритмом, створеним спеціально для комп’ютера, і завдяки цьому Лавлейс вважається першою програмісткою.

Представлення алгоритмів

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

Словесний опис. Цей підхід використовує природну мову для пояснення кроків алгоритму. Він зручний для неформального опису логіки, але не завжди достатньо чіткий для реалізації.

Приклад словесного опису: алгоритм пошуку мінімального елемента в списку:

1. Ініціалізувати змінну min першим елементом списку.
2. Перебрати всі елементи списку.
3. Якщо поточний елемент менший за min, оновити min.
4. Повернути min після завершення перебору.

Псевдокод — це проміжна форма запису алгоритму, що поєднує елементи природної мови та програмного коду.

алгоритм ЗнайтиМінімальне(список):
    min = список[0]
    для кожного елемента у списку:
        якщо елемент < min:
            min = елемент
    повернути min

Блок-схема або граф-схема — це графічне представлення алгоритму, яке використовує стандартні фігури для позначення операцій, умов та потоків управління.

Основні елементи блок-схем:

• Овал — початок і завершення алгоритму.
• Паралелограм — введення/виведення даних.
• Прямокутник — операція або дія.
• Ромб — перевірка умови.
• Стрілки — порядок виконання команд.

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

def find_minimum(lst):
    min_value = lst[0]
    for item in lst:
        if item < min_value:
            min_value = item
    return min_value

Порівняння методів представлення:

Рекомендація: при розробці складних алгоритмів корисно комбінувати кілька методів представлення, що покращить розуміння, оптимізацію та реалізацію алгоритму.

Джерела

• By Ada Lovelace - http://www.sophiararebooks.com/pictures/3544a.jpg, Public Domain, https://commons.wikimedia.org/w/index.php?curid=37285970
• File:Нотация Ландау.svg. (2023, July 19). Wikimedia Commons. Retrieved 11:09, March 5, 2025.