算法的时间复杂度：找到最长的回文子串的长度

Question

我写了一个小的PHP函数来查找字符串最长的回文子串的长度。为了避免很多循环，我使用了递归。

算法背后的思想是，循环遍历数组和每个中心（包括字符和字符之间的中心），以递归方式检查左右插入符号值是否相等。当字符不相等或其中一个插入符不在数组（字）范围内时，特定中心的迭代结束。

问题：

1）你能写一个数学计算，用来解释这个算法的时间复杂度吗？在我理解它的O（n ^ 2），但我很难通过详细的计算确认。

2）您如何看待这个解决方案，任何改进建议（考虑到它仅用于练习45分钟）？从时间复杂度的角度来看，有更好的方法吗？

为了简化示例，我放弃了一些输入检查（更多注释）。

谢谢你们，干杯。

<?php
/**
 * Find length of the longest palindromic substring of a string.
 *
 * O(n^2)
 * questions by developer
 * 1) Is the solution meant to be case sensitive? (no)
 * 2) Do phrase palindromes need to be taken into account? (no)
 * 3) What about punctuation? (no)
 */

$input = 'tttabcbarabb';
$input2 = 'taat';
$input3 = 'aaaaaa';
$input4 = 'ccc';
$input5 = 'bbbb';
$input6 = 'axvfdaaaaagdgre';
$input7 = 'adsasdabcgeeegcbgtrhtyjtj';

function getLenRecursive($l, $r, $word)
{
    if ($word === null || strlen($word) === 0) {
        return 0;
    }

    if ($l < 0 || !isset($word[$r]) || $word[$l] != $word[$r]) {
        $longest = ($r - 1) - ($l + 1) + 1;
        return !$longest ? 1 : $longest;
    }

    --$l;
    ++$r;

    return getLenRecursive($l, $r, $word);
}

function getLongestPalSubstrLength($inp)
{
    if ($inp === null || strlen($inp) === 0) {
        return 0;
    }

    $longestLength = 1;
    for ($i = 0; $i <= strlen($inp); $i++) {
        $l = $i - 1;
        $r = $i + 1;
        $length = getLenRecursive($l, $r, $inp); # around char
        if ($i > 0) {
            $length2 = getLenRecursive($l, $i, $inp); # around center
            $longerOne = $length > $length2 ? $length : $length2;
        } else {
            $longerOne = $length;
        }
        $longestLength = $longerOne > $longestLength ? $longerOne : $longestLength;
}

    return $longestLength;
}

echo 'expected: 5, got: ';
var_dump(getLongestPalSubstrLength($input));
echo 'expected: 4, got: ';
var_dump(getLongestPalSubstrLength($input2));
echo 'expected: 6, got: ';
var_dump(getLongestPalSubstrLength($input3));
echo 'expected: 3, got: ';
var_dump(getLongestPalSubstrLength($input4));
echo 'expected: 4, got: ';
var_dump(getLongestPalSubstrLength($input5));
echo 'expected: 5, got: ';
var_dump(getLongestPalSubstrLength($input6));
echo 'expected: 9, got: ';
var_dump(getLongestPalSubstrLength($input7));

Answer 1

您的代码实际上不需要递归。一个简单的while循环就可以了。是的，复杂性是O（N ^ 2）。您有N个选项可供选择中间点。递归步骤的数量从1到N / 2。所有的总和是2 *（N / 2）*（n / 2 + 1）/ 2，即O（N ^ 2）。

对于代码审查，我不会在这里做递归，因为它相当简单，你根本不需要堆栈。我会用while循环替换它（仍然在一个单独的函数中，以使代码更具可读性）。