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

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

Складність алгоритму — це           [кількісна, якісна, часова, ємнісна] характеристика, яка визначає        [час, об'єм, розмір, темп], що необхідний для виконання алгоритму, і        [об’єм, розмір, темп, час] пам’яті, необхідний для його розміщення.

Часова складність – це:                         .

Ємнісна складність – це           [кількість, якість, розмір, величина] умовних одиниць пам’яті, необхідних для роботи           [алгоритму, пам'яті, моделі, проблеми].

Часова та ємнісна складність тісно пов’язані між собою. Обидві є функціями від                       .

Оцінюється складність при прагненні розміру вхідних даних до                 [нескінченності, незалежності, неприпустимості, невиконаності].

Терміном елементарна операція позначають присвоювання та операції над значеннями простих типів:

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

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

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

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

Лінійну складність O(n) мають алгоритми, час виконання яких             [лінійно, пропорційно, квадратично, кубічно] залежить від кількості вхідних даних.

Квадратична складність O(n²) визначається, якщо час роботи алгоритму зростає пропорційно          [квадрату, кубу, різниці, сумі] кількості оброблюваних елементів.

Кубічна складність O(n³) визначається, якщо час роботи алгоритму зростає пропорційно          [кубу, квадрату, сумі, добутку] кількості оброблюваних елементів.

Американська вчена в галузі інформатики, відома своєю роботою у галузі об’єктно-орієнтованого програмування і графічних інтерфейсів та розробкою мови програмування Smalltalk.