Можно ли решить задачу быстрее чем за линейное время?

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

Понимаете ли вы, откуда берётся нижняя граница O(n) и за счёт чего её обходят: свойства данных, подходящая структура, предобработка. Следом просят показать это на коллекциях .NET и назвать сложность конкретных методов.

Как отвечать

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

• бинарный поиск: Array.BinarySearch и List<T>.BinarySearch за O(log n) на отсортированных данных. Если элемента нет, метод возвращает отрицательное число, побитовое дополнение которого даёт место вставки;
• хэш: HashSet<T>.Contains и Dictionary<TKey, TValue>.TryGetValue за O(1) в среднем. Скорость держится на корректных GetHashCode и Equals у ключа;
• деревья: SortedDictionary и SortedSet дают O(log n) на поиск и вставку, у SortedSet есть ещё выборка диапазона через GetViewBetween;
• очередь с приоритетом: PriorityQueue<TElement, TPriority> (с .NET 6) отдаёт минимум через Peek() за O(1);
• предобработка: префиксные суммы или индекс по ключу строятся один раз за O(n), дальше каждый запрос стоит O(1).

Отдельно про LINQ: Count() на ICollection<T> берёт готовое свойство Count, а ленивую последовательность перебирает целиком. Contains на List<T> линейный, и в цикле это даёт O(n²).

И оговорка про константы: Span<T> и векторизованный IndexOf в .NET работают в разы быстрее наивного цикла, но асимптотика у них остаётся O(n). Это ускорение, а не другой класс сложности.

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

Приводят Counting Sort и Radix Sort как пример «быстрее линейного». Они линейные, то есть быстрее O(n log n), но не быстрее O(n).

Говорят, что обход разреженного графа быстрее O(n). BFS и DFS стоят O(V + E), и каждую достижимую вершину всё равно нужно посетить.

Сортируют ради одного поиска. Array.Sort стоит O(n log n), линейный проход по массиву дешевле.