Зная сложность соревновательного программирования
Предпосылка: Анализ сложности времени
Как правило, при решении задач конкурентного программирования на различных сайтах наиболее сложной задачей является написание кода желаемой сложности, в противном случае программа получит TLE ( Превышен лимит времени ). Наивное решение почти никогда не принимается. Итак, как узнать, какая сложность приемлема?
Ответ на этот вопрос напрямую связан с количеством операций, которые разрешено выполнять в течение секунды. Большинство сайтов в наши дни допускают 10 8 операций в секунду , только несколько сайтов все еще допускают 10 7 операций. Определив количество операций, которые можно выполнить, найдите подходящую сложность, посмотрев на ограничения, указанные в задаче.
Пример:
Дан массив A [] и число x, найдите в A [] пару с суммой x.
где N:
1) 1 <= N <= 10 3 2) 1 <= N <= 10 5 3) 1 <= N <= 10 8
Для случая 1
Наивное решение, использующее два цикла for, работает, поскольку дает нам сложность O (N 2 ), которая даже в худшем случае будет выполнять 10 6 операций, которые намного меньше 10 8 . Конечно, в этом случае также допустимы O (N) и O (NlogN).
Для случая 2
Мы должны подумать о лучшем решении, чем O (N 2 ), так как в худшем случае оно выполнит 10 10 операций, поскольку N равно 10 5 . Таким образом, приемлемая для этого случая сложность - это либо O (NlogN), что составляет примерно 10 6 (10 5 * ~ 10) операций значительно меньше 10 8, либо O (N).
Для случая 3
Даже O (NlogN) дает нам TLE, поскольку он выполняет ~ 10 9 операций, которые больше 10 8 . Таким образом, единственное приемлемое решение - O (N), которое в худшем случае выполнит 10 ^ 8 операций.
Код для данной проблемы можно найти по адресу: https://www.geeksforgeeks.org/write-ac-program-that-given-a-set-a-of-n-numbers-and-another-number-x -определяет-существуют-ли-существуют-два-элемента-в-s-чья-сумма-точно-x /
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.