Карточка Junior Задачи на Kotlin обновлено
Ограничения и сложность
Вопрос
Какая сложность обычно проходит при n до 10, 20, 500, 5000, 10^6?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
n ≤ 10: O(n!) перебор. n ≤ 20: O(2^n). n ≤ 500: O(n³). n ≤ 5000: O(n²). n ≤ 10^6: O(n log n) или O(n). Ориентир около 10^8 простых операций в секунду, на JVM учитывайте прогрев и ввод.
Ответ
n ≤ 10: O(n!) перебор. n ≤ 20: O(2^n). n ≤ 500: O(n³). n ≤ 5000: O(n²). n ≤ 10^6: O(n log n) или O(n). Ориентир около 10^8 простых операций в секунду, на JVM учитывайте прогрев и ввод.
Разбор
n ≤ 10: O(n!) перебор. n ≤ 20: O(2^n). n ≤ 500: O(n³). n ≤ 5000: O(n²). n ≤ 10^6: O(n log n) или O(n). Ориентир около 10^8 простых операций в секунду, на JVM учитывайте прогрев и ввод.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.