Esta es mi solución en javascript para eliminar todas las apariciones de 'b' y 'ac' en una cadena, pero puedo encontrar la complejidad del tiempo, especialmente. al eliminar todas las apariciones de 'ac'. ¿Alguien podría explicar?
function removeChars(input) { let result = input; result = result.replaceAll('b', ''); // tc = O(n) where n is length of string. string of all b's while(result.indexOf('ac') !== -1) { // number of ac ? what if aacacacc result = result.replaceAll('ac', ''); // replaceAll has time complexity of O(n) } return result; // space ~ O(n) }Podemos considerar uno de los casos más especiales: input = aaa...aaaccc...ccc .
Suponga que la cadena de entrada tiene una longitud n , habrá n / 2 ocurrencias para 'ac'. La declaración de result = result.replaceAll('ac', ''); se ejecutará n / 2 veces. La complejidad temporal de replaceAll() es O(n), por lo que la complejidad temporal general es O(n^2).
El método indexOf() devuelve el primer índice en el que se puede encontrar un elemento dado en la matriz, o -1 si no está presente, por lo que el peor de los casos será O(N) , y replaceAll dentro del bucle para que Big -O es O(N) , la Voluntad total O(N^2)
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf