Складність алгоритмів: графіки зростання кількості операцій
Оберіть алгоритми й подивіться, як зростає кількість порівнянь зі збільшенням розміру списку.
Як це працює
Складність показує, як швидко зростає кількість операцій зі збільшенням розміру даних n. Це важливіше за час роботи на конкретному комп’ютері.
Для O(n²) подвоєння n збільшує роботу вчетверо; для O(n) — вдвічі; для O(log n) майже нічого.
Приклади
- Лише сортування — відкрити з цими значеннями
Часті запитання
Що означає O(n²)?
Кількість операцій зростає приблизно як квадрат розміру даних.
Чому вбудоване sort() швидше за бульбашку?
Воно використовує ефективніші алгоритми порядку n·log n, а бульбашка має порядок n².
Читайте також: Поняття складності алгоритмів.