Для такого рода задач онлайн-программирования с ограничением времени выполнения вашей программы входные данные теста будут включать в себя несколько довольно больших примеров, и обычно устанавливается ограничение по времени, чтобы вам не приходилось сжимать каждую последнюю миллисекунду производительностииз вашего кода, но вы должны написать алгоритм с достаточно низкой вычислительной сложностью . Чтобы ответить, почему ваш алгоритм истекает, мы можем проанализировать его, чтобы найти его вычислительную сложность, используя big O нотация .
Сначала мы можем пометить каждый отдельный оператор с его сложностью, где n этодлина s1 и m равна длине s2:
def scramble(s1,s2):
result = True # O(1)
for character in s2: # loop runs O(m) times
if character not in s1: # O(n) to search characters in s1
return False # O(1)
i = s1.index(character) # O(n) to search characters in s1
s1 = s1[0:i] + s1[i+1:] # O(n) to build a new string
return result # O(1)
Тогда общая сложность составляет O (1 + m * (n + 1 + n + n) + 1)или, проще говоря, O (m * n). Это не эффективно для этой проблемы.
Ключ к тому, почему альтернативный алгоритм работает быстрее, заключается в том, что set(s2) содержит только отличные символы из строки s2. Это важно, потому что алфавит, из которого образованы эти строки, имеет постоянный, ограниченный размер;предположительно 26 для строчных букв. Учитывая это, внешний цикл альтернативного алгоритма фактически выполняется не более 26 раз:
def scramble(s1,s2):
for letter in set(s2): # O(m) to build a set
# loop runs O(1) times
if s1.count(letter) < s2.count(letter): # O(n) + O(m) to count
# chars from s1 and s2
return False # O(1)
return True # O(1)
Это означает, что сложность альтернативного алгоритма составляет O (m + 1 * (n + m + 1) + 1) илиболее просто O (m + n), что означает, что он асимптотически более эффективен, чем ваш алгоритм.