Нотация Big O

Big O описывает рост, а не точную скорость. На интервью ожидают, что вы определите размер входа, найдёте доминирующую операцию и объясните, почему константы можно отбросить только после ясной модели. Главный компромисс — точность против полезности: Big O скрывает железо и константы, но помогает сравнивать алгоритмы при росте входа.

Пример:

					const seen = new Set();
for (const value of values) seen.add(value);
				

Цикл имеет O(n) по времени в среднем и O(n) по памяти, потому что каждый элемент обрабатывается один раз и хранится максимум один раз.

На интервью: разделяйте лучший, средний, худший и амортизированный случаи. Упоминайте, когда вложенный цикл всё ещё O(n), потому что указатели движутся монотонно.

Типовые ошибки: называть любой вложенный цикл O(n²); игнорировать память; забывать амортизированное поведение у динамических массивов и hash table.

Чеклист:

• Определите n перед оценкой.
• Назовите время и память.
• Разделите best, average, worst и amortized cases.
• Проговорите допущение о структуре данных.