Quiero verificar mis suposiciones sobre la complejidad del tiempo y el espacio de dos implementaciones diferentes de funciones de palíndromo válidas en JavaScript.
En la primera implementación estamos usando una función auxiliar y solo pasamos punteros
const isPalindrome = str => { return isPalindromeHelper(str, 0, str.length - 1); } const isPalindromeHelper = (str, start, end) => { if (end - start < 1) return true; return str[start] === str[end] && isPalindromeHelper(str, start + 1, end - 1) }En este caso, asumo que la complejidad del tiempo es O(N) y la complejidad del espacio también es O(N).
Sin embargo, digamos que en lugar de pasar punteros estamos cortando la cadena cada vez. Y digamos que el slice es una operación O(n).
const isPalindrome = str => { if (str.length <= 1) return true; if (str[0] !== str[str.length - 1]) return false; return isPalindrome(str.slice(1, str.length - 1)); }¿Esto empujaría la complejidad del tiempo y el espacio a O (N ^ 2) si el segmento fuera una operación O (N)? ¿El tiempo debido a la complejidad del tiempo de la porción y el espacio aumentaría ya que constantemente estamos creando nuevas cadenas?
¿Esto empujaría la complejidad del tiempo y el espacio a O (N ^ 2) si el segmento fuera una operación O (N)? Tiempo debido a la complejidad del tiempo de la
slice...
Sí, si asumimos que slice tiene una complejidad temporal de O(𝑛), entonces tenemos O(𝑛−1 + 𝑛−2 + 𝑛−3 + ... + 1) que es O(𝑛²)
... y el espacio aumentaría ya que constantemente estamos creando nuevas cadenas?
Nuevamente, si asumimos que el slice asigna nueva memoria para el segmento, entonces tenemos (con la misma fórmula) un uso de espacio de O(𝑛²)
Como las cadenas son inmutables, un motor de JavaScript puede beneficiarse de la memoria que ya tiene la cadena y no asignar realmente memoria nueva para segmentos. Esto se llama internamiento de cadenas . Esto podría devolver la complejidad tanto del tiempo como del espacio a O(𝑛). Sin embargo, dado que no existe ningún requisito en la especificación del lenguaje EcmaScript para hacer esto, no tenemos ninguna garantía.
Ambos son operaciones recursivas y se ejecutan a lo largo de toda la cadena (n) n/2 veces desde que comienzan en 0 y en n - 1 y se ejecutan hasta que se encuentran en n/2 .
En la notación O, esto significaría que ambos son O(n) ya que puedes ignorar la constante 2 .