Временная сложность алгоритма: найти длину самой длинной палиндромной подстроки - PullRequest
Новая
       19

Временная сложность алгоритма: найти длину самой длинной палиндромной подстроки

0 голосов
/ 11 сентября 2018

Я написал небольшую 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));

1 Ответ

0 голосов
/ 11 сентября 2018

Ваш код не обязательно должен быть рекурсивным. Простой цикл while вполне подойдет. Да, сложность O (N ^ 2). У вас есть N вариантов для выбора средней точки. Количество шагов рекурсии варьируется от 1 до N / 2. Сумма всего, что составляет 2 * (N / 2) * (n / 2 + 1) / 2, и это O (N ^ 2).

Для проверки кода я бы здесь не делал рекурсию, поскольку она довольно проста и стек вообще не нужен. Я бы заменил его на цикл while (все еще в отдельной функции, чтобы сделать код более читабельным).

...