Кількість операцій для алгоритмів різної складності
Асимптотична складність алгоритму - спосіб оцінки обчислювальної складності алгоритму «з точністю до константи», застосовуваний в теорії складності. Зазвичай записується в нотації «великого О».
Широко застосовується, так як точна оцінка складності в елементарних операціях часто складна (в тому числі залежить і від того, що прийняти за елементарну операцію - одну дію в конкретній мові програмування, процесорний такт), а також не має сенсу при великих обсягах вхідних даних, коли медленнорастущие частини тимчасової функції практично перестають впливати на загальний обсяг виконуваної роботи.
Найчастіше використовується асимптотична оцінка часу роботи алгоритму зверху, що записується як O (f (n)), де n - обсяг вхідних даних. Якщо прийняти функцію часу роботи алгоритму в залежності від обсягу вхідних даних як F (n), то можна сказати, що починаючи з певного числа N для всіх n> N виконується нерівність | F (n) | <= |N*f(n)|. иными словами, с некоторого момента функция F(n) растет не быстрее. чем N*f(n), где N — константа.
Оцінки складності алгоритмів:
- Логарифмічна складність - залежить від вхідних даних n як N * log (n), зокрема, таку складність має операція пошуку в індексованих масиві, швидкого зведення в довільну ступінь. На практиці частіше зустрічається складність N * n * log (n).
- Поліноміальна складність - залежить від вхідних даних n як N * n ^ c, де c - деяка конкретна ступінь. Вказується лише старша ступінь полінома, так як з ростом n менші ступені перестають істотно впливати. Наприклад, подвійний перебір масиву має складність O (n²), реалізація методу Шульце для n кандидатів - O (n³).
- Експоненціальна складність - залежить від вхідних даних n як N * e ^ n. Використання алгоритмів з такою складністю намагаються уникати, це складні завдання на графах, складні операції пошуку по декількох таблицях в MySQL і т. Д.
Можливі й більш високі складності, наприклад N * n.