React Frontend Developer

Question 1

Какую сложность будет иметь решение с объектом-словарём

Accepted Answer

Операции доступа к объекту-словарю (Object или Map) обычно имеют O(1). Это связано с использованием хеш-таблиц. Однако в худшем случае сложность может деградировать до O(n) из-за коллизий. На практике для большинства задач доступ считается константным.

Question 2

Как уменьшить сложность с O(n²) до O(n)?

Accepted Answer

Чтобы уменьшить сложность с O(n²) до O(n), нужно заменить вложенные циклы на более эффективные структуры данных, например, хеш-таблицы. Вместо перебора всех пар элементов можно использовать один проход с записью данных в словарь. Это позволяет находить нужные элементы за константное время. Такой подход часто применяется в задачах поиска пар, подсчёта частот или проверки дубликатов.

Question 3

Что такое линейная сложность? Чему соответствует O(n)?

Accepted Answer

Линейная сложность O(n) означает, что время выполнения алгоритма растет прямо пропорционально размеру входных данных n. Например, если на входе 10 элементов, алгоритм делает 10 операций, а на 100 элементах — 100 операций. Это типично для простого перебора массива в поиске значения.

Вопросы React Frontend Developer