Алгоритмы с нуля
Сортировка и поиск: свободное припоминание
Припоминание сильнее перечитывания. Для каждого вопроса проговорите или запишите полный ответ по памяти, прежде чем открыть эталон — именно усилие припоминания закрепляет материал.
Восстановите ключевые идеи юнита — сортировка как препроцессинг, почему merge sort и quicksort ведут себя так по-разному, инвариант binary search и бинарный поиск по ответу — не подглядывая в уроки.
- 01Почему сортировку называют препроцессингом и каково правило, стоит ли сортировать?
- 02Все простые сортировки O(n²), но insertion sort всё равно полезна. Почему и чем она отличается от selection sort на почти отсортированном входе?
- 03Почему merge sort O(n log n) на любом входе и чем вы за эту гарантию платите?
- 04Quicksort O(n log n) в среднем, но O(n²) в худшем случае. Объясните разрыв и как продакшен-код от него защищается.
- 05Сформулируйте инвариант binary search и три классических бага, его нарушающих.
- 06Что такое «бинарный поиск по ответу» и какое предусловие должно выполняться для его корректности?
Если вы смогли восстановить каждый ответ по памяти, вы держите стержень юнита: сортируйте только ради переиспользования порядка; insertion sort адаптируется, а selection sort — никогда; merge sort гарантирует O(n log n) и stable-свойство ценой O(n) памяти; quicksort меняет худший случай на in-place скорость и защищает его умным выбором pivot; а binary search — хоть по массиву, хоть по монотонному пространству ответов — живёт или умирает по своему включающему инварианту.