Алгоритмы с нуля
Мышление и сложность: тест на припоминание
Припоминание сильнее перечитывания. На каждый вопрос проговори или запиши полный ответ по памяти, прежде чем открыть образцовый — именно усилие извлечения закрепляет идею.
Восстанови костяк юнита — зачем считаем шаги, что Big-O сохраняет и отбрасывает, лестницу классов сложности, компромисс время-память и как ограничения выбирают подход — не подсматривая в уроки.
- 01Почему мы измеряем алгоритм его темпом роста (Big-O), а не реальным временем по часам?
- 02Сформулируй правило нахождения Big-O по числу шагов и примени его к 3n² + 100n + 50.
- 03Как комбинировать сложности для последовательного кода и для вложенных циклов и почему разница так велика?
- 04Назови распространённые классы сложности от быстрейшего к медленнейшему и где практический обрыв.
- 05Объясни компромисс время-память на примере поиска дубликата и как решить, какую сторону взять.
- 06Как входное ограничение n подсказывает, какую сложность брать, с одним разобранным примером?
Если ты смог восстановить каждый ответ по памяти, ты держишь костяк юнита: мы измеряем рост, а не время по часам; Big-O сохраняет доминирующий член и отбрасывает константы; последовательные фазы складываются, а вложенные циклы перемножаются; лестница классов идёт от O(1) до O(n!) с практическим обрывом на O(n²); время и память торгуются между собой, и решает связывающее ограничение; а граница входа n напрямую отображается в сложность, которую нужно достичь. Оценивай стоимость до того, как что-либо запустишь.