foundation
Время, память и амортизированный анализ
Оценивайте доминирующие операции, дополнительную память, амортизированную цену и лучший, средний и худший случаи.
Анализ сложности начинается с именования размеров входа и операции, которая растет вместе с ними. Time complexity считает доминирующую работу; space complexity считает дополнительную память, а не всегда сам input. Амортизированный анализ объясняет последовательности, где редкие дорогие операции компенсируются множеством дешевых.
На интервью: Интервьюеры ожидают, что вы разделяете best, average и worst cases, проговариваете допущения про hashing или sorting и меняете оценку при добавлении cache, recursion или preprocessing.
Типовые ошибки: Не называйте O(n), пока не определили n. Nested loops не всегда O(n squared), если каждый pointer движется монотонно. Recursive решения требуют stack space, а JavaScript recursion может упереться в call stack limit.
Чеклист:
- Определите каждый размер входа.
- Назовите доминирующую операцию.
- Посчитайте auxiliary memory.
- Объясните разницу amortized и worst case.