Что такое большой O в этом javascript рекурсивном решении, чтобы проверить, является ли строка палиндромом?

Question

Я нашел несколько очень полезных решений для написания функции Javascript, которая рекурсивно проверяет, является ли строка палиндромом здесь . Я хотел бы знать, какова будет временная и пространственная сложность следующего решения. Можете ли вы объяснить, как каждая строка способствует большой O?

function isPalindrome(string) {
    if (string.length < 2) return true;
    if (string[0] === string[string.length - 1]) {
        return isPalindrome(string.slice(1, string.length - 1))
        }
    return false;
}

Answer 1

Сначала может показаться, что ваша функция O (n), потому что вы вызываете ее рекурсивно n / 2 раза. Однако в каждом вызове вы также используете string.slice, который имеет сложность O (n). Из-за этого ваша функция на самом деле O (n ^ 2)

Answer 2

Вы рекурсивно вызываете функцию n / 2 раза, где n - длина строки, поскольку вы удаляете первую и последнюю запись строки на каждой итерации.

Следовательно, сложность будет O(n/2) = O(n), и у вас есть не более 3 операций при каждом вызове функции. Это умножит все это на константу, которая не изменит сложности.

РЕДАКТИРОВАТЬ: как отмечено в комментариях и другом ответе, одна из этих операций string.slice. Вы должны проверить на сложность этого, потому что это умножится также и может изменить полную сложность. Если slice является O (1) константой, то в целом у вас будет O (n). Если slice равно O (n), то в целом это будет O (n ^ 2).

Для сложности пространства вы создаете много массивов. Я дам вам подробности, но мне хочется сказать, что это O(n^2) с первого взгляда.

Схема вычислений: первый массив имеет размер n, затем n-2, n-4, суммируйте все это с помощью некоторых математических формул суммирования.

подсказка: n + (n-1) + (n-2) + ... - это n * (n + 1) / 2, то есть O(n^2), что должно дать достаточно «ощущения», что это тоже O(n^2).