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

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，并返回在SRC中找到SEA的每个字符的索引。如果 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。这样就只剩下位置 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) 搜索字符串为 RBRRBRBBBRRRBBRRBBBRRBBBRR。它应该返回 [-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 ]，但不幸的是它没有 =(

优化：

我想停止搜索当“索引”列表完全充满-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"))

Answer 1

您可以在 O(n + m) 中完成此操作，其中 m 是 SEA 中的字符数，n code> 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

则：在 SRC 中查找 B：在 last = 1 处找到
打印1，设置last = 2。

在SRC中查找B：在last = 4处找到，打印4，设置last = 5< /代码>。

在SRC中查找B：在last = 6处找到，打印6，设置last = 7< /代码>。完毕。

---

至于算法的复杂性，我无法提供非常正式的分析，但我会尝试解释我将如何进行分析。

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

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

所以你有：

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

乍一看，你是在搜索、递归和回溯吗？

我相信为源字符串创建一个 后缀数组 是一个好主意。
构造 后缀数组 的复杂度为 O(nlogn)。定位子字符串的时间复杂度为 O(logn)。