回文划分 II 的时间和 Space 复杂度

Question

所以我正在解决这个 LeetCode 问题 - https://leetcode.com/problems/palindrome-partitioning-ii/ 并提出了以下最朴素的暴力递归解决方案。现在，我知道如何记住这个解决方案，并通过动态规划尽可能地做到最好。但是为了找到进一步解决方案的 time/space 复杂性，我想看看这个解决方案有多糟糕，我在多个地方查找但未能找到具体的 T/S 复杂性回答。

def minCut(s: str) -> int:
    def is_palindrome(start, end):
        while start < end:
            if not s[start] == s[end]:
                return False
            start += 1
            end -= 1
        return True

    def dfs_helper(start, end):
        if start >= end:
            return 0

        if is_palindrome(start, end):
            return 0
        curr_min = inf
        
        # this is the meat of the solution and what is the time complexity of this
        for x in range(start, end):
            curr_min = min(curr_min, 1 + dfs_helper(start, x) + dfs_helper(x + 1, end))
        return curr_min

    return dfs_helper(0, len(s) - 1)

Answer 1

让我们来看看最坏的情况，即回文检查不允许我们提前出局。

为了写出递归关系，假设n = end - start，这样n就是要处理的序列的长度。我假设索引数组访问是常数时间。

is_palindrome 将在 O(end - start) = O(n) 步中检查回文。

dfs_helper 对于长度为 n 的子序列，调用 is_palindrome 一次，然后进行 2n 次长度从 0 到 n - 1 的递归调用，每次调用两次，加上通常的常量开销为了简单起见，我将省略。

所以，我们有

T(0) = 1
T(n) = O(n) + 2 * (sum of T(x) for x=0 to n-1)
# and for simplicity, I will just use
T(n) = n + 2 * (sum of T(x) for x=0 to n-1)

这个模式已经 has to be at least exponential。我们可以看看接下来的几个步骤：

T(1)  =   3 = 1 + 2 *  1  =  1 + 2 * (T(0))
T(2)  =  10 = 2 + 2 *  4  =  2 + 2 * (T(0) + T(1))
T(3)  =  31 = 3 + 2 * 14  =  3 + 2 * (T(0) + T(1) + T(2))
T(4)  =  94 = 4 + 2 * 45  =  4 + 2 * (T(0) + T(1) + T(2) + T(3))

看起来好像增长速度大约与 3^n 一样快。我们还可以证明对于 n > 2:

T(n) = n + 2 * (sum of T(x) for x=0 to n-1)
T(n) = n + 2 * (T(0) + T(1) + ... + T(n-1))
T(n) = n + 2 * (T(0) + T(1) + ... + T(n-2)) + 2 * T(n-1)
T(n) = 1 +  n-1 + 2 * (T(0) + T(1) + ... + T(n-2))  +  2 * T(n-1)

# with
T(n-1) = n-1 + 2 * (sum of T(x) for x=0 to n-2)
T(n-1) = n-1 + 2 * (T(0) + T(1) + ... + T(n-2))

# we can substitute:
T(n) = 1 + T(n-1) + 2 * T(n-1)
T(n) = 1 + 3 * T(n-1)

所以，如果我没记错的话，渐近时间复杂度应该在θ(3^n)，或者，允许我开个玩笑，even worse than O(no)。

对于 Space 复杂性：您的函数没有显式分配任何内存。因此，只有递归的恒定开销（假设 python 没有优化它）。这里重要的一点是两个递归步骤会一个接一个发生，这样我们就得到了递归：

S(0) = 1
S(n) = 1 + S(n-1)

这给了我们 θ(n) 的 space 复杂度。

回文划分 II 的时间和 Space 复杂度

Time and Space complexity of Palindrome Partitioning II

python

time-complexity

space-complexity