Сложность алгоритмов и связные списки с нуля

Что в ролике
Если нужно пройти алгоритмическое собеседование, этот разбор даёт базу для оценки качества кода — от порядка роста времени до связного списка как структуры данных. Автор начинает с того, что нельзя мерить алгоритм секундомером, и показывает на замедленном Google, что одинаковый ответ при плохой сложности бесполезен. Дальше он объясняет Big O, Omega и Theta, а заодно — почему считать нужно по худшему случаю. На простых примерах получаются O(1) для поиска середины и O(n) для максимума, а пузырьковая сортировка упирается в O(n²). Merge sort даёт O(n log n), бинарный поиск — O(log n), рекурсивный Фибоначчи растёт экспоненциально. В части памяти считается стек вызовов и вспомогательный массив merge sort, поэтому итоговая space complexity там O(n). Следующий блок вводит односвязный список через узел с данными и ссылкой, объясняет голову, хвост и печать итеративно и рекурсивно. Затем разбираются вставка и удаление в голове, хвосте и по индексу, удаление по значению, с чек-листами для пустых списков и сравнением с массивами.
Практика
- Что получишь
- Ты сможешь по коду определять порядок роста времени и памяти, объяснять Big O для сортировок и рекурсии, а также писать базовые операции односвязного списка: вставку, удаление и печать.
- Первый шаг
- Начни с ручного прогона трёх узлов связного списка на бумаге и в Python-визуализаторе, затем повтори вставку в голову и хвост.
- Цифры
- —10^8 — столько операций в секунду, по ориентиру автора, обычно допускают онлайн-судьи
- —100 000 элементов — вход, для которого бинарный поиск делает около 17 сравнений
- —n ≤ 12 и n ≤ 25 — границы из таблицы автора, при которых можно пробовать O(n!) и O(2^n)
- Честно
- Автор не продаёт курс, но многократно просит подписку, лайки и комментарии, а ссылки на ноутбуки и заметки лежат в описании. Большая часть объяснения держится на экранных визуализациях и живом коде: без видео повторить логику указателей по пересказу сложно. Оценка Фибоначчи как O(2^n) дана с упрощающим допущением, точнее было бы золотое сечение в степени n.
Если слова незнакомы — 6 терминов
- Big Oспособ записать, насколько быстро растёт время или память относительно размера входа
- Omegaнижняя граница роста, оценка лучшего случая
- Thetaточный порядок роста, когда верхняя и нижняя границы совпадают
- space complexityпамять, которую алгоритм занимает в зависимости от размера входа
- стек вызововпамять, которую занимают незавершённые вызовы функций в рекурсии
- односвязный списокцепочка узлов, где каждый узел хранит данные и ссылку на следующий
Компоненты
8 шт.Формат: пошаговый урок · для новичков · уверенность разметки 0.88 · источник