Что хотят услышать интервьюеры:

Нужно понимать, что у разных коллекций стоимость операций отличается и зависит от внутренней реализации. Обычно ожидают знание амортизированного O(1), линейного O(n), логарифмического O(log n) и того, какие операции для каких коллекций быстрые или дорогие. Важно уметь оценивать не только добавление, но и поиск, удаление и доступ по индексу.

Определение:

Временная сложность — это оценка того, как растёт время выполнения операции при увеличении размера коллекции. Для стандартных коллекций C# она определяется структурой данных внутри: массивы и List<T> дают быстрый доступ по индексу, связные списки лучше подходят для вставок в известное место, а Dictionary<TKey, TValue> и HashSet<T> обычно обеспечивают быстрый поиск по ключу за счёт хеш-таблицы.

Пример использования:

Если нужно часто искать элемент по ключу, лучше использовать Dictionary<TKey, TValue>, а не List<T>. Если нужна частая вставка в середину и известно место вставки, может подойти LinkedList<T>, но поиск узла всё равно будет дорогим.

var list = new List<int> { 10, 20, 30 };
int x = list[1];           // O(1)

bool found = list.Contains(20); // O(n)

var dict = new Dictionary<int, string>
{
    [1] = "one",
    [2] = "two"
};

string value = dict[2];    // обычно O(1)
bool hasKey = dict.ContainsKey(1); // обычно O(1)

Пояснение кода:

В примере доступ к list[1] выполняется быстро, потому что List<T> хранит элементы в массиве и умеет сразу перейти к нужному индексу.
Метод Contains у списка просматривает элементы по одному, поэтому при росте коллекции время увеличивается линейно.
У Dictionary<TKey, TValue> поиск по ключу обычно выполняется за константное время благодаря вычислению хеша и обращению к нужной корзине, поэтому такие операции быстрее при больших объёмах данных.

Ключевые моменты:

List<T>: доступ по индексу — O(1), поиск и удаление по значению — O(n).
Dictionary<TKey, TValue> и HashSet<T>: поиск, вставка и удаление обычно O(1) в среднем, но в худшем случае могут деградировать.
LinkedList<T>: вставка/удаление узла при наличии ссылки на него — O(1), поиск узла — O(n).
SortedDictionary / структуры с сортировкой: операции обычно O(log n) за счёт дерева.
При оценке сложности важно учитывать не только саму коллекцию, но и конкретную операцию.
Для корректного выбора коллекции нужно сопоставлять частоту поиска, вставки, удаления и доступа по индексу.

Как определить временную сложность различных операций с элементами стандартных коллекций?