Часова складність
З Вікіпедії, безкоштовно encyclopedia
Часова складність алгоритму в комп'ютерних науках є обчислювальною складністю алгоритму, яка описує час потрібний для виконання алгоритму. Вона зазвичай визначається шляхом підрахунку кількості елементарних операцій, виконуваних алгоритмом, при цьому вважають, що кожна елементарна операція виконується за фіксовану кількість часу. Таким чином, кількість часу і кількість елементарних операцій, необхідних для виконання алгоритму, відрізняються постійним множником.
Оскільки час роботи алгоритму може відрізнятися на вхідних даних одного розміру, то зазвичай розглядається найгірший випадок складності, який відповідає максимальному часу, необхідного для виконання при вхідних даних заданого розміру. Менш поширеною і, як правило, явно вказаною є складність алгоритму у середньому[en], яка є середньою величиною часу на вхідні дані даного розміру (це має сенс, оскільки існує лише скінченне число можливих вхідних даних даного розміру). В обох випадках часова складність алгоритму є функцією від розміру вхідних даних.[1] Оскільки ці функції, як правило, важко точно розрахувати, а час роботи у випадку невеликого розміру вхідних даних, не завжди прогнозований, тому зазвичай оцінюють поведінку складності при збільшенні розміру вхідних даних, тобто асимптотичну поведінку складності алгоритму. Це пояснює, чому зазвичай часову складність часто описують за допомогою нотації великого О, зазвичай і т. д., де n відповідає розміру вхідних даних в одиницях вимірювання або в бітах, які потрібні для їх представлення.
Алгоритмічна складність класифікується відповідно до типу функції, яка її описує в нотації великого О. Наприклад, алгоритм зі складністю є алгоритмом лінійної складності, а алгоритм зі складністю для деякої константи є алгоритмом поліноміальної складності.