Какова асимптотика при нескольких проходах по списку?

Что проверяют

Понимаете ли вы, что константы в O-нотации отбрасываются, и при этом не путаете последовательные проходы с вложенными. Следом обычно спрашивают, что будет, если число проходов само зависит от размера данных, и почему на практике два прохода всё-таки могут быть заметно медленнее одного.

Как отвечать

• k последовательных проходов: каждый стоит O(n), вместе O(k·n). Если k фиксировано (найти минимум, потом максимум, потом среднее), это O(n): три прохода и один проход с тремя переменными в одном классе сложности;
• k зависит от данных: проход для каждого из m запросов даёт O(m·n), и отбрасывать m нельзя. Если m порядка n, это уже O(n²);
• вложенные проходы: для каждого элемента обходите список снова, получается O(n²). Сюда же относится скрытая вложенность: x in some_list или list.index() внутри цикла сами по себе линейны;
• память: несколько проходов не требуют дополнительной памяти, если вы не копируете список на каждом шаге.

Дальше покажите, что понимаете практику. В Python один проход циклом for часто медленнее трёх векторизованных вызовов numpy, хотя по O они равны: константа у интерпретатора в десятки раз выше. Когда данные не помещаются в память, каждый проход означает повторное чтение с диска, и тогда их число важнее асимптотики. В Spark каждое действие пересчитывает цепочку трансформаций заново, поэтому перед несколькими проходами по одному датафрейму вызывают cache() или persist().

Где спотыкаются

Отвечают «O(2n)» и останавливаются. Правильно сказать O(n) и пояснить, что двойка уходит в константу.

Пропускают скрытую линейную операцию. Цикл по списку с проверкой in по другому списку выглядит как один проход, а на деле это O(n·m).

Забывают, что генератор или итератор по файлу проходится один раз. Второй проход по исчерпанному генератору молча вернёт пустоту, и ошибка всплывёт уже в метриках.