Я разработал рекурсивный алгоритм и записал его на Python. Когда я измеряю время работы с другими параметрами, это, кажется, занимает экспоненциальное время. Более того; это займет больше получаса, чтобы закончить с маленькими числами, такими как 50. (Я не ждал, пока это не закончится, но это, кажется, не заканчивается через разумное количество времени, думаю, это экспоненциально).
Итак, мне любопытно, насколько сложен этот алгоритм во время выполнения. Может ли кто-нибудь помочь мне вывести уравнение T (n, m)? Или вычислить биг-о?
Алгоритм приведен ниже:
# parameters:
# search string, the index where we left on the search string, source string, index where we left on the source string,
# and the indexes array, which keeps track of the indexes found for the characters
def find(search, searchIndex, source, sourceIndex, indexes):
found = None
if searchIndex < len(search): # if we haven't reached the end of the search string yet
found = False
while sourceIndex < len(source): # loop thru the source, from where we left off
if search[searchIndex] == source[sourceIndex]: # if there is a character match
# recursively look for the next character of search string
# to see if it can be found in the remaining part of the source string
if find(search, searchIndex + 1, source, sourceIndex + 1, indexes):
# we have found it
found = True # set found = true
# if an index for the character in search string has never been found before.
# i.e if this is the first time we are finding a place for that current character
if indexes[searchIndex] is None:
indexes[searchIndex] = sourceIndex # set the index where a match is found
# otherwise, if an index has been set before but it's different from what
# we are trying to set right now. so that character can be at multiple places.
elif indexes[searchIndex] != sourceIndex:
indexes[searchIndex] = -1 # then set it to -1.
# increment sourceIndex at each iteration so as to look for the remaining part of the source string.
sourceIndex = sourceIndex + 1
return found if found is not None else True
def theCards(N, colors):
# allcards: a list 1..N of characters where allcards[i] is 'R' if i is a prime number, 'B' otherwise.
# so in this example where N=7, allcards=['B','R','R','B','R','B','R']
allcards = ['R' if isPrime(i) else 'B' for i in range(1, N + 1)]
# indexes is initially None.
indexes = [None] * len(colors)
find(colors, 0, allcards, 0, indexes)
return indexes
if __name__ == "__main__":
print theCards(7, list("BBB"))
Я не знаю, нужно ли понимать проблему и алгоритм, чтобы получить наихудшее время выполнения, но вот проблема, которую я пытался решить:
Проблема:
Учитывая исходную строку SRC и строку поиска SEA, найдите подпоследовательность SEA в SRC и верните индексы того, где каждый символ SEA был найден в SRC. Если символ в SEA может находиться в нескольких местах в SRC, вернуть -1 для этой позиции символов.
Например;
если исходная строка - BRRBRBR (N = 7), а строка поиска - BBB:
тогда первый «B» в «BBB» может появиться с индексом 0 в строке поиска. Второй «B» может быть в индексе 3 строки поиска, а последний «B» может быть в 5-й позиции. Более того; не существует других альтернатив для позиций символов «BBB», и поэтому алгоритм возвращает [0,3,5].
В другом случае, где исходная строка - BRRBRB (N = 6), а строка поиска - RBR:
первый 'R' в 'RBR' может быть в позиции 1 или 2. Это оставляет только позицию 3 для 'B' и позицию 4 для последнего 'R'. Тогда первый «R» может быть в нескольких местах, это место неоднозначно. Два других символа, B и R, занимают только одно место. Таким образом, алгоритм возвращает [-1,4,5].
Случай, когда алгоритм не завершается и не длится вечно, это когда исходная строка имеет вид ['B', 'R', 'R', 'B', 'R', 'B', 'R', «B», «B», «B», «R», «B», «R», «B», «B», «B», «R», «B», «R», «B» ',' B ',' B ',' R ',' B ',' B ',' B ',' B ',' B ',' R ',' B ',' R ',' B ', 'B', 'B', 'B', 'B', 'R', 'B', 'B', 'B', 'R', 'B', 'R', 'B', 'B ',' B ',' R ',' B ',' B ',' B ',' B ',' B ',' R ',' B ',' B ',' B ',' B ', 'B'] (N = 58)
и строка поиска - это RBRRBRBBRBRRBBRRBBBRRBBBRR. Должно возвращаться [-1, -1, -1, -1, -1, -1, -1, -1, 17, 18, 19, 23, -1, -1, -1, -1, -1 , -1, -1, -1, -1, -1, -1, -1, 47, 53], но, к сожалению, это не так = (
Оптимизация:
Я думал о прекращении поиска, когда список 'indexes' был полностью заполнен -1. Но это влияет только в лучшем случае (или, может быть, в среднем), но не в худшем. Как можно еще оптимизировать этот алгоритм. Я знаю, что существует полиномиальное решение этой проблемы.
Более важным, чем оптимизация, мне действительно любопытно уравнение времени выполнения T (n, m), где n и m - длины строк источника и поиска.
Если бы вы могли читать до здесь, большое спасибо! =)
EDIT - реализовано решение IVIad:
def find2(search, source):
indexes = list()
last = 0
for ch in search:
if last >= len(source):
break
while last < len(source) and source[last] != ch:
last = last + 1
indexes.append(last)
last = last + 1
return indexes
def theCards(N, colors):
# allcards: a list 1..N of characters where allcards[i] is 'R' if i is a prime number, 'B' otherwise.
allcards = ['R' if isPrime(i) else 'B' for i in range(1, N + 1)]
indexes = find2(colors, allcards) # find the indexes of the first occurrences of the characters
colors.reverse() # now reverse both strings
allcards.reverse()
# and find the indexes of the first occurrences of the characters, again, but in reversed order
indexesreversed = find2(colors, allcards)
indexesreversed.reverse() # reverse back the resulting list of indexes
indexesreversed = [len(allcards) - i - 1 for i in indexesreversed] # fix the indices
# return -1 if the indices are different when strings are reversed
return [indexes[i] + 1 if indexes[i] == indexesreversed[i] else - 1 for i in range(0, len(indexes))]
if __name__ == "__main__":
print theCards(495, list("RBRRBRBBRBRRBBRRBBBRRBBBRR"))