# python – 我的算法的运行时间复杂度 – 我如何计算并进一步优化算法？

Python写下来.当我用不同的参数测量运行时间时,它似乎需要指数时间.此外;以50这样的小数字结束需要半个多小时.(我没等到它完成,但它似乎没有在合理的时间内完成,猜测它是指数级的).

``````# 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"))
``````

‘RBR’的第一个’R’可以位于1或2位置.这只留下’B’的位置3和最后’R’的位置4.然后,第一个’R’可以在多个地方,它的位置是不明确的.另外两个字符B和R只有一个地方.所以算法返回[-1,4,5].

搜索字符串是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,-1,47,53],但遗憾的是它不=(

``````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"))
``````

``````last = 1
for i = 1 to m do
while SRC[last] != SEA[i]
++last

print last
++last (skip this match)
``````

For instance; if the source string is BRRBRBR (N=7) and the search string is BBB

``````i = 1: calls find(2, 2), find(3, 3), ..., find(m, n)
find(2, 2) calls find(3, 3), ..., find(m, n)
find(3, 3) calls find(4, 4), ..., find(m, n)
find(4, 4) calls find(5, 5), ..., find(m, n)
...
total calls: O(m^m)
i = 2: same, but start from find(2, 3).
...
i = n: same
``````