运行时间我的算法的复杂性 - 我如何计算并进一步优化算法？

Question

我设计了一个递归算法，并在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，发现在SRC的子SEA并返回我指出SEA的每个角色在SRC中的位置。如果SEA中的字符可以在SRC中的多个位置，则返回-1作为该字符位置。

例如;如果源字符串是BRRBRBR（N = 7）并且搜索字符串是BBB： ，那么'BBB'中的第一个'B'可以出现在搜索字符串中的索引0处。第二个'B'可以在搜索字符串的索引3处，最后'B'可以在第5个位置。此外;对于字符'BBB'的位置不存在其他替代方案，因此算法返回[0,3,5]。在另一种情况下，如果源字符串是BRRBRB（N = 6）并且搜索字符串是RBR： 'RBR'的第一个'R'可以在位置1或2。 'B'和最后一个'R'的位置4。那么，第一个'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]，但不幸的是它不=（

优化：

我认为当'索引'列表完全满-1s时，停止搜索，但这只影响最好的情况（或者可能是平均情况），而不是最坏的情况，我怎么能进一步优化这个算法？存在一个多项式解决这个问题

比优化更重要的是，我真的很好奇运行时间的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")) 

Answer 1

您可以在O(n + m)，其中m是字符的SEA数量，以及n做字符的SRC数量：

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

    print last 
    ++last (skip this match) 

基本上，每一个字符SEA，发现其在SRC位置，但只能在找到前一个字符的位置之后进行扫描。

例如;如果源字符串是BRRBRBR（N = 7）和搜索字符串是BBB

然后：找到在SRCB：在last = 1 打印1发现，设置last = 2。

查找SRCB：在last = 4发现，打印4，设置last = 5。

查找B in SRC：found at last = 6，print 6，set last = 7。完成。至于你的算法的复杂性，我不能提供一个非常正式的分析，但我会试着解释我将如何去做。

假设SRC和SEA以及它们之间的所有字符相同。因此，我们可以消除while循环中的条件。另请注意，while循环执行n次。

请注意，对于第一个字符，您可以拨打find(1, 1), ... find(m, n)。但是这些也会启动它们的while循环并进行自己的递归调用。每个find(i, j)将在其while循环中为i = 1 to n进行递归调用O(m)。但这些反过来又会自己做出更多的递归调用，从而导致一种导致指数复杂度的“雪崩效应”。

所以，你必须：

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 

总复杂因而看起来像O(n*m^m)。我希望这是有道理的，我没有犯任何错误。

Answer 2

这简直是最长公共子序列。这可以通过动态编程来实现，以获得比指数时间少很多的时间。在你的情况下，当LCS返回SEA的长度时，你知道序列SEA存在于SRC中，在修改算法时保存它们的索引是微不足道的事情。这里有一个很好的解释。 http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Answer 3

从快速的样子，你正在寻找，递归和回溯？

我认为创建一个suffix array为您的源字符串将是一个好主意。
构造suffix array具有O（nlogn）的复杂性。定位子串具有O（logn）时间复杂度。