Estaba trabajando en un problema de leetcode y recibí comentarios de que el siguiente bloque de código tiene una complejidad de tiempo O(n^3). ¿Alguien puede ayudarme a explicarme cómo es esto? Cuento dos bucles que me llevaron a creer que esto era O (n ^ 2).
var longestPalindrome = function(s) { let maxString = ""; let originalString = s; let reversedString = s.split("").reverse().join(""); for (let i = 0; i < s.length; i++){ for (let j = i+1; j < s.length+1; j++){ if (i<j){ let iteratedSubstring = originalString.substring(i,j) if (reversedString.includes(iteratedSubstring) && (iteratedSubstring === iteratedSubstring.split("").reverse().join("")) ){ iteratedSubstring.length > maxString.length ? maxString = iteratedSubstring: maxString = maxString } } } } return maxString }El bloque if se ejecuta O(𝑛²) veces, pero el cuerpo de ese bloque no es O(1):
originalString.substring(i,j) puede tener una complejidad de tiempo O(𝑗−𝑖) (dependiendo de la implementación), por lo que promediaría una complejidad de tiempo de O(𝑛). Ver también: ¿La subcadena de Javascript es virtual?reversedString.includes(iteratedSubstring) iteratedSubstring) tiene una complejidad de tiempo O(𝑛)iteratedSubstring.split("") tiene una complejidad de tiempo O(𝑛).reverse() tiene una complejidad de tiempo O(𝑛).join("") tiene complejidad de tiempo O(𝑛) Entonces, hay varias razones por las que if el bloque tiene una complejidad de tiempo de O(n), da una complejidad de tiempo general de O(𝑛³)