Сложности операций в односвязном списке, list, dict и строках Python
Сравните сложности добавления и доступа для односвязного списка, Python list, Python dict и конкатенации строк. Где нужен amortized O(1), а где важен worst-case?
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
В односвязном списке вставка в начало O(1), а вставка в конец O(n), если нет указателя на хвост. Python list - динамический массив: append amortized O(1), доступ по индексу O(1), вставка в начало/середину O(n). Dict обычно O(1) в среднем, строки immutable и при конкатенации копируются.
Полный разбор
Для односвязного списка важно проговорить допущение. Если есть только указатель на голову, вставка в начало O(1), а вставка в конец требует пройти весь список и стоит O(n). Если заранее есть ссылка на нужный предыдущий узел или tail pointer, сама перестановка указателей O(1).
Python list - это динамический массив. Доступ по индексу O(1), append в конец amortized O(1), но отдельный append может стоить O(n), когда массив расширяется. Вставка в начало или середину O(n), потому что элементы нужно сдвигать.
Python dict - хэш-таблица: lookup и insert в среднем/amortized O(1), но есть caveats про коллизии, resize и hashability ключей. Строки в Python immutable, поэтому повторная конкатенация создает новые строки и копирует данные; для большого числа добавлений обычно собирают список и делают join.
Теория
Главное - явно отделять средний, worst-case и amortized случаи, а также проговаривать устройство структуры данных.
Типичные ошибки
- Говорить, что append в linked list всегда O(1), не уточнив tail pointer.
- Забыть про resize у динамического массива.
- Считать повторную конкатенацию строк бесплатной.
Как отвечать на собеседовании
- Сначала назовите допущение про указатели в linked list.
- Для Python list и dict используйте слово amortized.