Entradas

Mostrando las entradas etiquetadas como Algorithms

Algoritmos: Big O

Imagen
En palabras llanas podemos considerar la Big O como un sistema de clasificación para el comportamiento de nuestros algoritmos en función de la cantidad de datos con los que trabajan. Teniendo lo anterior en mente podemos representar la Big O como una gran fotografía panorámica sin detalles superfluos sobre el comportamiento de un algoritmo en función de sus datos de entrada. Ejemplo : Tengo 3 marcos de clasificación que son perros, gatos y pollos. Cada imagen de un  animal aquí es distinta en sus detalles, pero cada una representa de forma general un tipo de animal. Sin importar sus diferencias en detalle o cantidad yo puedo resumirlas en una simple silueta que indique a que tipo de animal pertenece. Gato Perro Pollo El ejemplo anterior muestra la idea general detrás del uso de la Big O en la informática. Podemos clasificar los algoritmos sin enfocarnos en detalles superfluos, simplemente viendo su silueta o características esenciales puede decir a que Big O pertenece. ¿Cuáles son...

Técnicas para Algoritmos: Sliding Windows #2

Imagen
D ada una cadena(st) y un patrón(pt), averigüe si la cadena contiene alguna permutación del patrón. Detalles:  Si una cadena tiene 'n' caracteres distintos, tendrá n! Permutaciones. Del ejemplo anterior podemos decir que una cadena de 3 caracteres tiene un total de  3! = 3 *2*1 = 6 permutaciones. La permutación se define como la reorganización de los caracteres de la cadena. Por ejemplo, "abc" tiene las siguientes seis permutaciones: abc acb bac bca cab cba Escenarios de prueba:  Escenario #1:  Entrada: st=" oidbcaf ", pt="abc" (Strings). Salida:   true (Boolean). Explicación: La cadena contiene "bca" , que es una permutación del patrón dado. Escenario #2:  Entrada: st="odicf", pt="dc" (Strings). Salida:   false (Boolean). Explicación: No hay permutación del patrón presente en la cadena dada como una subcadena.. Escenario #3:  Entrada: st="bcdxabcdy", pt="bcdyabcdx" (Strings). Salida:   tru...

Técnicas para Algoritmos: Sliding Windows #1

Imagen
Estos ejercicios que presentaremos a continuación se fundamentan en la estrategia Slinding Windows. Aplicar esta técnica a problemas donde sea necesario recorrer una lista de elementos en donde tengas que buscar o calcular algo a partir de sub arreglos con elementos consecutivos de un tamaño k elementos. Escenario de pruebas: Dado un arreglo, encuentra el promedio de todos los sub arreglos de tamaño k. Input: arr = [1, 3, 2, 6, -1, 4, 1, 8, 2];  k= 5 Output: [ 2.2, 2.8, 2.4, 3.6, 2.8] Este problema puede tener varias soluciones posibles que pueden ser válidas,  en esta introducción tomaremos dos soluciones posibles. La primera solución no sigue ninguna estrategia en particular que le llamaremos fuerza bruta (FB) y la segunda solución si sigue una estrategia en este caso Sliding Windows (SW). Con estas dos estrategias vamos a resaltar la importancia de tener un plan a seguir bien pensado para resolver este tipo de problemas.  Problema (fácil): Promedio de sub arreglos ...