재귀 알고리즘을 설계하여 파이썬에서 작성했습니다. 다른 매개 변수로 실행 시간을 측정 할 때 기하 급수적 인 시간이 걸릴 것 같습니다. 더욱이; 50과 같은 작은 숫자로 끝나는 데는 30 분 이상이 소요됩니다. (끝날 때까지 기다리지는 않았지만 합리적인 시간 내에 끝내지 않는 것으로 보입니다. 기하 급수적이라고 생각하십시오).내 알고리즘의 실행 시간 복잡성 -이를 어떻게 계산하고 알고리즘을 최적화 할 수 있습니까?
그래서이 알고리즘의 실행 시간 복잡성에 대해 궁금합니다. 누군가가 방정식 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를 감안할 때, SRC의 서브 시퀀스 SEA를 발견하고 난을 반환 해결하기 위해 시도 SEA의 각 문자가 SRC에서 발견 된 위치의 ndexes. SEA의 문자가 SRC의 여러 위치에있을 수 있으면 해당 문자 위치에 대해 -1을 반환합니다.
예를 들면; 소스 문자열이 BRRBRBR (N = 7)이고 검색 문자열이 BBB 인 경우 : 'BBB'의 첫 번째 'B'는 검색 문자열의 색인 0에 나타날 수 있습니다. 두 번째 'B'는 검색 문자열의 색인 3에 있고 마지막 'B'는 다섯 번째 위치에있을 수 있습니다. 더욱이; 문자 'BBB'의 위치에 대한 다른 대안이 없으므로 알고리즘은 [0,3,5]를 반환합니다.
소스 문자열이 BRBRBRB (N = 6)이고 검색 문자열이 RBR 인 경우 : 'RBR'의 첫 번째 'R'은 1 또는 2 위치에있을 수 있습니다. 마지막 'R'은 'B'이고 위치는 4입니다. 그러면 첫 번째 'R'은 여러 위치에있을 수 있습니다. 그 장소는 모호합니다. 다른 두 문자 인 B와 R은 단 하나의 장소 만 가지고 있습니다. 따라서 알고리즘은 [-1,4,5]를 반환합니다.
소스 스트링이 [ 'B', 'R', 'B', 'R', 'B', 'R' B, B, R, B, R, B, B, B, R, B, R, B ','B ','B ','B ','B ','R ','B ','R ','B ' 'B', 'R', 'B', 'B', 'B', 'R', 'B', 'R', 'B' B ','B ','B ','B ','R ','B ','B ','B ','B ' , 'B'] (N = 58) 이고 검색 문자열은 RBRRBRBBRBRRBBRRBBBRRBBBRR입니다. [-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), 그러나 불행히도 = (
최적화는 않는다 :
I는 생각 'indexes'리스트가 -1로 완전히 채워 졌을 때 검색을 멈춘다.하지만 그것은 최악의 경우에만 영향을 미치지 만 최악의 경우에는 영향을 미치지 않는다. 어떻게이 알고리즘을 더 최적화 할 수 있는가? 이 문제에 대한 다항식 솔루션이 존재합니다. 최적화보다 더 중요한 것은, 실행 시간의 T (n, m) 방정식에 대해 궁금합니다. n과 m은 다음과 같습니다. 소스 및 검색 문자열의 길이
여기까지 읽을 수 있다면 대단히 감사합니다! =)
편집은 - 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"))
아직 알고리즘을 이해하지 못했지만 O (n^2) 인 것처럼 보입니다. – Gabe
@ Murat- "이 문제에 대한 다항식 해결책이 있다는 것을 알고 있습니다." 나는 호기심이 많지 않다. 어떻게 알 수 있니? – Justin
| V | ad의 대답을 받아 들여야합니다. 정확한 답입니다. 코드와 설명 때문에 당신이하려는 일을 정확히 이해하지 못했습니다. 그래서 제가 제공 한 답은 약간 더 복잡한 문제입니다. –