Часова складність алгоритму
Часова́ скла́дність алгори́тму — характеристика продуктивності алгоритму, що застосовується в алгоритмів теорії; визначається кількістю елементарних операцій, які потрібно виконати для реалізації алгоритму. При цьому вважають, що кожна елементарна операція виконується за однаковий час.
Характеристика
Часова складність алгоритму зазвичай визначається виразами з використанням О-нотації, яка виключає коефіцієнти і члени меншого порядку.
Поняття «О-нотація» вживають у математиці для порівняння асимптотичної поведінки функцій. Формально O (f (n)) означає, що час роботи алгоритму (або обсяг займаної пам’яті) зростає залежно від обсягу вхідних даних не швидше, ніж деяка константа, помножена на f (n). Ця математична нотація відома також як «нотація Ландау»: названа на честь математика Е. Ландау (1877–1938, Німеччина). Нотація вживається в теорії складності обчислень, інформатиці та математиці.
Для аналізу трудомісткості алгоритму часто використовують асимптотичні позначення, які показують залежність часу роботи алгоритму від обсягу оброблюваної інформації, маскуючи при цьому конкретні коефіцієнти. Така оцінка називається складністю алгоритму і дає змогу порівняти переваги використання різних алгоритмів для вхідних даних великого обсягу.
Часова складність найчастіше оцінюється шляхом підрахунку кількості елементарних операцій, які виконує алгоритм, за умови, що кожна така операція потребує однакового часу, тобто повний час роботи алгоритму і кількість виконуваних елементарних операцій відрізняються максимум на постійний множник.
Точні значення часу роботи алгоритму залежать від його конкретної реалізації, тоді як О (f (n)) є характеристикою самого алгоритму. Оскільки продуктивність алгоритму на вхідних даних однакового обсягу може відрізнятися, то зазвичай часову складність T(n) оцінюють для найгіршого випадку і визначають як максимальний час, необхідний для обробки алгоритмом будь-якої множини з n елементів.
Приклади
- Якщо час роботи алгоритму не залежить від обсягу вхідних даних, то його часову складність позначають як O (1); приклад — визначення значення першого елемента масиву.
- Лінійна складність O (n): час роботи алгоритму лінійно зростає зі збільшенням оброблюваних елементів; приклад — алгоритм пошуку найбільшого елемента в невідсортованому масиві.
- Логарифмічна складність O (log n): час роботи алгоритму зростає пропорційно логарифму кількості оброблюваних елементів; приклад — бінарний пошук у відсортованому масиві.
- Квадратична складність O (n2): час роботи алгоритму зростає пропорційно квадрату кількості оброблюваних елементів; приклад — алгоритм сортування вставками, що виконує два вкладені цикли перебору масиву.
- Експоненційна складність O (xn): час роботи алгоритму зростає пропорційно експоненті кількості оброблюваних елементів; приклади — т. зв. задача комівояжера, семантико-залежні задачі обробки природномовного тексту.
Використання
Часова складність застосовується в наукових дослідженнях для об’єктивного порівняння алгоритмів різних авторів. Таке порівняння не враховує частоту окремих елементарних операцій та відмінності у часі виконання на реальних обчислювальних пристроях (наприклад, на конкретному процесорі). Тому пришвидшення виконання алгоритмів з визначеною часовою складністю можливе шляхом створення спеціалізованого високопродуктивного обладнання.
Література
- Нікітченко М. С., Шкільняк С. С. Математична логіка та теорія алгоритмів. Київ : Київський університет, 2008. 528 с.
- Горлова Т. М. Теорія алгоритмів. Київ : Національний університет харчових технологій, 2015. 95 с.
- Гладун А. Я., Рогушина Ю. В. Семантичні технології: принципи та практики. Київ : ТОВ «ВД «АДЕФ-Україна», 2016. 308 с.
Автор ВУЕ
Покликання на цю статтю: Рогушина Ю. В. Часова складність алгоритму // Велика українська енциклопедія. URL: https://vue.gov.ua/Часова складність алгоритму (дата звернення: 28.04.2024).
Статус гасла: Оприлюднено
Оприлюднено: 24.01.2020
Важливо!
Ворог не зупиняється у гібридній війні і постійно атакує наш інформаційний простір фейками.
Ми закликаємо послуговуватися інформацією лише з офіційних сторінок органів влади.
Збережіть собі офіційні сторінки Національної поліції України та обласних управлінь поліції, аби оперативно отримувати правдиву інформацію.
Отримуйте інформацію тільки з офіційних сайтів
Офіс Президента України
Верховна Рада України
Кабінет Міністрів України
Служба безпеки України
Міністерство оборони України
Міністерство внутрішніх справ України
Національна поліція України
