Выбор ответа Middle Задачи на Kotlin спрашивают часто обновлено
Сложность по ограничениям
Вопрос
В задаче n ≤ 2·10^5, лимит 2 секунды. Какая сложность решения ожидается?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n log n) или O(n). Ориентир: около 10^8 простых операций в секунду. n² при n = 2·10^5 это 4·10^10 операций, не успеет. n log n это около 3.5·10^6, с запасом.
Варианты ответа
- O(n log n) или O(n)правильный ответ
- O(n³) с малой константой
- O(n²), успеет за 2 секунды
- O(2^n) с отсечениями
Разбор
Ориентир: около 10^8 простых операций в секунду. n² при n = 2·10^5 это 4·10^10 операций, не успеет. n log n это около 3.5·10^6, с запасом. Поэтому ограничение 10^5-10^6 почти всегда намекает на сортировку, бинарный поиск, хеш-таблицу, два указателя или линейную динамику.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.