Сопоставление Middle Задачи на Java обновлено
Ограничения и допустимая сложность
Вопрос
Сопоставьте размер входа и сложность, которая обычно укладывается в 1-2 секунды.
Попробуйте сами
Нажмите слева, потом подходящее справа.
Показать ответ и разбор
Коротко
Ориентир: за секунду Java выполняет порядка 10⁸ простых операций. Отсюда оценка по ограничениям ещё до написания кода.
Правильные пары
n ≤ 20O(2ⁿ · n)
n ≤ 500O(n³)
n ≤ 5000O(n²)
n ≤ 2·10⁵O(n log n)
n ≤ 10⁸O(n) с простыми операциями
Разбор
Ориентир: за секунду Java выполняет порядка 10⁸ простых операций. Отсюда оценка по ограничениям ещё до написания кода.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.