Урок 57-58. Поняття складності алгоритму

Перегляньте та законспектуйте презентацію

Теоретичний матеріал

Який час потрібний для виконання програми, що реалізує певний алгоритм? Чи можна взагалі  отримати результати обчислення за даним алгоритмом на комп’ютері? На подібні питання відповідає теорія алгоритмів - розділ інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв.

Що таке складність алгоритму? Інтуїтивно можна виділити такі основні складові складності алгоритму:

1. Логічна складність — кількість людино-місяців, витрачених на створення алгоритму.

2. Статична складність — довжина опису алгоритмів (кількість операторів).

3. Часова складність — час виконання алгоритму.

4. Ємнісна складність — кількість умовних одиниць пам'яті, необхідних для роботи алгоритму.

Складність алгоритму дозволяє визначитися з вибором ефективного алгоритму серед тих, що побудовані для розв’язання конкретної проблеми.

 Складність алгоритму – це кількісна характеристика, що відображує споживані алгоритмом ресурси під час свого виконання.

Оцінка складності

Складність алгоритмів зазвичай оцінюють за часом виконання або по використовуваній пам’яті. В обох випадках складність залежить від розмірів вхідних даних: масив з 100 елементів буде оброблений швидше, ніж аналогічний з 1000. При цьому мова йде не про точний час обчислень, який залежить від процесора, типу даних, мови програмування тощо. Оцінюється складність при прагненні розміру вхідних даних до нескінченності.

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

При цьому вважають, що кожна елементарна операція виконується за однаковий час.

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

Часова складність алгоритму зазвичай визначається виразом O (f (n)) (або так званої О-нотації).  Вираз O(f(n)) означає, що час виконання алгоритму зростає з тією ж швидкістю, що і функція  f(n).

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

• Константна складність O(1): якщо час роботи алгоритму не залежить від обсягу вхідних даних, то його часову складність позначають як O(1); приклад — визначення значення третього елемента масиву, для чого не потрібно ні запам’ятовувати елементи, ні проходити по ним декілька разів. Завжди потрібно просто дочекатися в потоці вхідних даних третій елемент і це буде результатом, на обчислення якого для будь-якої кількості даних потрібний один і той же час.

• Лінійна складність O(n): подвоєння розміру задачі подвоїть і необхідний час; приклади — алгоритм пошуку найбільшого елемента в невідсортованому масиві, для чого потрібно переглянути всі n елементів масиву; алгоритм додавання/віднімання чисел з  n цифр.

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

• Кубічна складність O(n3): подвоєння розміру задачі збільшує необхідний час у вісім разів. Припустимо, певним алгоритмом потрібно виконати  4n3+7n  умовних операцій, щоб обробити n елементів вхідних даних. При збільшенні n на час роботи буде значно більше впливати зведення n в куб, ніж множення його на 4 або ж додавання 7n.  

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

Розв’язання. Нехай n – кількість символів в послідовності. Алгоритм буде послідовно перевіряти, чи немає одиниці в поточному місці заданої послідовності, а потім рухатися далі, поки вхід не скінчиться. Оскільки одиниця дійсно може бути тільки одна, для отримання точної відповіді на це питання в гіршому випадку доведеться перевірити всі n символів входу. Таким чином, алгоритм має складність O(n),  іншими словами, він лінійний.

Приклад:

Розглянемо код, який для масиву A[n, n]  знаходить максимальний елемент у кожному рядку.

 for i:=1 to N do  
    begin
      max:=A[i,1];
      for j:=1 to N do    
if A[i,j]>max then  max:=A[i,j];
      writeln(max);
    end;

У цьому алгоритмі змінна і змінюється від 1 до  n. При кожній зміні і, змінна j теж змінюється від 1 до  n. Під час кожної з  n ітерацій зовнішнього циклу, внутрішній цикл теж виконується  n раз. Загальна кількість ітерацій внутрішнього циклу дорівнює  n*n. Це визначає складність алгоритму O(n2).

Перегляньте і виконайте інтерактивні завдання

За підручником

"Інформатика, 9 клас" (Й.Я. Ривкінд та їнші):

• • Прочитайте та розберіть теоретичний матеріал пункту 5.3 (стор. 265-267).

Для моніторингу засвоєння знань пройдіть тестування

• https://vseosvita.ua/test/start/bco026