Как работает калькулятор
Калькулятор вызывает твою функцию на входах размером 32, 64, 128 и так далее, каждый раз вдвое больше, и замеряет каждый размер.
Быстрые вызовы замеряются пачками, потому что часы браузера тикают раз в десятую долю миллисекунды. Каждый вызов получает свежий вход, так что функция, сортирующая на месте, не ускорит свой следующий вызов.
Потом он подгоняет под замеры каждый частый класс и выбирает тот, что объясняет их лучше всего. Если два класса подходят почти одинаково, он так и пишет.
Частые классы сложности, от быстрых к медленным
Грубый ориентир: современная машина делает около ста миллионов простых шагов в секунду. Последняя колонка показывает самый большой вход, который укладывается в секунду.
| Класс | Типичный код | n за секунду |
|---|---|---|
| O(1) | Прочитать один элемент, найти в хеш-таблице | любой |
| O(log n) | Бинарный поиск, поиск в сбалансированном дереве | любой |
| O(n) | Один проход по входу, два указателя | 10⁸ |
| O(n log n) | Сортировка, куча из n элементов | 5·10⁶ |
| O(n²) | Два вложенных цикла по входу | 10⁴ |
| O(n³) | Три вложенных цикла, Флойд-Уоршелл | 450 |
| O(2ⁿ) | Все подмножества, наивная рекурсия | 26 |
Чего замер сказать не может
Калькулятор меряет один вид входа. Быстрая сортировка работает за O(n log n) на случайных данных и за O(n²) на некоторых отсортированных, так что пробуй тот вход, который получает твоя задача.
O(n) и O(n log n) трудно различить на коротком диапазоне, потому что log n растёт очень медленно. Если результат не уверен, он так и пишет.
Калькулятор меряет время, а не память. На собеседовании всё равно надо объяснить почему, и именно это стоит тренировать.
От замера к пониманию
Каждая страница паттерна называет его сложность и объясняет почему. Начни с той, на которую похожа твоя задача. Все паттерны на одной странице
Ссылка на эту страницу
Ставьте ссылку откуда удобно: со страницы курса, из README, из статьи. Скопируйте HTML:
<a href="https://algopath.pro/ru/big-o-calculator">Калькулятор сложности от AlgoPath</a>