К содержимому
Дайджест

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

Mayank Aggarwal·17 октября 2026·373:46
текст даёт основное можно повторить промо пошагово
Открыть на YouTube
Длинный учебный разбор для начинающих, который закрывает две темы: анализ времени и памяти алгоритмов и основы односвязного списка.

Что в ролике

Если нужно пройти алгоритмическое собеседование, этот разбор даёт базу для оценки качества кода — от порядка роста времени до связного списка как структуры данных. Автор начинает с того, что нельзя мерить алгоритм секундомером, и показывает на замедленном 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 терминов

Компоненты

8 шт.

Формат: пошаговый урок · для новичков · уверенность разметки 0.88 · источник