algorithm - 回文递归算法的时间复杂度

Question

我编写了这个递归函数来查找回文。

def palindrome(string):
    print("palindrome called with:"+string)
    if(len(string)<=3):
        return string[0]==string[-1]
    else:
        res=palindrome(string[1:-1])
        print("palindrome returned:"+str(res))
        return res

我现在已经找到这个算法的时间复杂度了。 我的问题 我的基本情况是否正确？ len<=3？ 我无法将此与互联网上随处可见的斐波那契和阶乘算法的经典示例联系起来。

Answer 1

是的，事实是只有您的基本情况是正确的。

所以你应该在这里做的是，检查第一个和最后一个字符是否相同，然后检查剩余的字符串是否也是回文。 但您绝不会检查这一点。

因此，只需对您的代码进行最少的更改，以下解决方案就可以工作，如果将空字符串作为参数传递，则该解决方案将失败。

def palindrome(string):
    print("palindrome called with:"+string)
    if(len(string)<=3):
        return string[0]==string[-1]
    else:
        if string[0] == string[-1]:
            res=palindrome(string[1:-1])
            print("palindrome returned:"+str(res))
            return res
        else:
            return False

当然，还有更好的写法。

def palindrome(s):
    return s == '' or (s[0]==s[-1] and palindrome(s[1:-1]))

我所做的就是，通过让它再进行两次递归调用，进一步减少您的基本情况。

现在，谈到时间复杂度，这两个代码是相同的。

在一个函数调用中，我们正在执行比较第一个字符和最后一个字符的 O(1) 操作。并且此递归调用最多执行 n/2 次。 n/2 因为在长度为 n 的字符串中，我们在每次调用中删除了 2 个字符。因此，总体复杂度将是 O(n)。(请注意，这会忽略每次递归调用中的字符串复制/切片。)

最后，您应该递归地避免这种情况，因为我们在每次递归调用之前都会创建一个新字符串(在切片时)。

def palindrome(s):
    def _palindrome(string, i, j):
        if i >= j:
            return True
        return string[i] == string[j] and _palindrome(string, i + 1, j - 1)
    return _palindrome(s, 0, len(s) - 1)

这不会在每次调用时都进行复制。因此，绝对是一个 O(n) 解决方案。