DIY Optimisation
Si a la mayoría de personas si les pides que encuentres un elemento en un array ordenada - seguramente te implementaran un algoritmo en O(N) que básicamente buscara por cada elemento del array hasta que lo encuentre y lo retorne.
Ahora, si a una persona le pides que encuentre el examen de un estudiante en una pila de exámenes que están ordenados alfabéticamente, seguramente de forma intuitiva aplique un algoritmo de búsqueda binaria O(Log N) en el cual empezara buscando mas o menos por el medio, y seguirá pivoteando hacia la izquierda o derecha de ese medio - y seguirá partiendo esa mitad en otra mitad hasta que eventualmente llegue al examen que necesita.
Por esta razón es muy importante considerar nuestra intuición al momento de diseñar un algoritmo. Sobre todo es importante dibujar varios ejemplos en papel e intentar resolverlo de esta forma, antes que intentar resolverlo en código. Piensa que en la mayoría de escenarios, un proceso que es lento para una persona, seguramente también sera lento para una computadora.
Inténtalo tu con este ejemplo: > Si te damos 2 Strings, la primera mas corta que la otra. Diseña un algoritmo que encuentre cualquier permutación de String (A) dentro de la segunda String (B) que es mas larga.
String a = “abbc”;
String b = “cbabadcbbabbcbabaabccbabc”;
Intenta pensar por un momento cómo lo resolverias? La mayoría de programadores intentarían resolverlo en código primero. Si eres como la mayoría de programadores que conozco, intentarías generar todas las permutaciones del String A, lo cual lleva un tiempo muy malo de O(A!), y después compararias linealmente con los pedazos del String B. Para darte noción - si el String A tiene 14 caracteres - esto conllevaría una cantidad mayor a 87 mil millones de permutaciones. Si agregas un carácter mas eso seria multiplicado por 15.
Mira este ejemplo que enseña todas las permutaciones de A dentro de B.
Cuando lo ves dibujado es mucho mas obvio que hay formas mas fáciles de encontrar estas permutaciones. Necesitas 4 caracteres - 1 a, 2 b, 1 c. Si empiezas de izquierda a derecha podrás notar que si encuentras uno de estos caracteres mientras traversas el String - podrás ver hacia ambos lados para ver si también tienes la cantidad necesaria de los otros para que se forme una permutación.
Intenta esta forma de optimización cuando resuelvas problemas. Recuerda de utilizar un ejemplo grande y después manualmente resuélvelo. Si ya has resuelto el problema en código - intenta compararlo con tu respuesta “manual”.
Ejemplo prestado del libro “Cracking the coding interview”