递归反向字符串的时间复杂度

Question

我想在Big O中找到以下代码的时间复杂度：

ReverseString(S,x,y)
if x < y
    swap(S,x,y)
    return ReverseString(S,x+1,y-1)

我得到的等式是

T(1) = 1
T(n) = 3 + T(n+1)+ T(n-1)

如果我是对的，我将如何解决这个问题。

如果我说的不对，正确的方程式是什么。

Answer 1

假设 x 和 y 是指向字符串结尾的指针，那么你的等式是错误的。这是一个简单的单次递归，但您假设了两次递归。此外，还存在使 T(n) 依赖于 T(n+1) 的严重问题；你真的不想在没有保证的有限有界减少的情况下 up 下标。

这样想：每次迭代都会使 x 和 y 在每一端彼此更接近一个字符。您的单个递归循环遍历字符串的两半。我会把关系写成

T(n) = 3 + T(n-1)

其中 n 是字符串长度的一半（如果为奇数则截断）。