Сохранёнки программиста
Фотография
нажмите — покажем
нажмите — покажем
Как читать Big O и находить лишнюю сложность в коде
Обстоятельная интерактивная статья объясняет Big O без секундомера: нотация показывает, как растёт время работы вместе с объёмом входа. O(1), O(log n), O(n) и O(n²) разобраны на графиках и примерах JavaScript.
Карта материала:
1. сумма циклом растёт линейно, а формула (n × (n + 1)) / 2 требует постоянного числа операций;
2. пузырьковая сортировка в худшем случае проходит n элементов n раз;
3. бинарный поиск отбрасывает половину вариантов за шаг и находит число среди миллиарда не более чем за 31 попытку.
Практический блок переносит теорию в код. Поиск в массиве имеет O(n), в Set: O(1), но создание new Set(items) требует O(n). Материал пригодится, чтобы оценивать алгоритмы по росту затрат и учитывать цену подготовки вместо единичных замеров.
6 · 348 ·