El análisis amortizado se utiliza para algoritmos en los que una operación ocasional es muy lenta, pero la mayoría de las demás operaciones son más rápidas. En Análisis amortizado, analizamos una secuencia de operaciones y garantizamos un tiempo promedio en el peor de los casos que es menor que el tiempo en el peor de … Continue reading «Análisis de Algoritmo | Conjunto 5 (Introducción al análisis amortizado)»
Hemos discutido el análisis asintótico y los peores, promedios y mejores casos de algoritmos . La idea principal del análisis asintótico es tener una medida de la eficiencia de los algoritmos que no dependan de las constantes específicas de la máquina y no requieran la implementación de algoritmos ni el tiempo que toman los programas … Continue reading «Análisis de Algoritmos | Conjunto 3 (notaciones asintóticas)»
¿Por qué análisis de rendimiento? Hay muchas cosas importantes que deben cuidarse, como la facilidad de uso, la modularidad, la seguridad, la mantenibilidad, etc. ¿Por qué preocuparse por el rendimiento? La respuesta a esto es simple, podemos tener todas las cosas anteriores solo si tenemos rendimiento. Entonces, el rendimiento es como una moneda a través … Continue reading «Análisis de Algoritmos | Conjunto 1 (Análisis asintótico)»
Hemos discutido el análisis asintótico , los casos peor, promedio y mejor y las notaciones asintóticas en publicaciones anteriores. En este post, se discute un análisis de programas iterativos con ejemplos simples. 1) O(1): la complejidad de tiempo de una función (o conjunto de declaraciones) se considera como O(1) si no contiene bucle, recursividad ni … Continue reading «Análisis de Algoritmos | Conjunto 4 (Análisis de bucles) – Part 1»
En la publicación anterior , discutimos cómo el análisis asintótico supera los problemas de la forma ingenua de analizar algoritmos. En esta publicación, tomaremos un ejemplo de búsqueda lineal y lo analizaremos utilizando el análisis asintótico. Podemos tener tres casos para analizar un algoritmo: 1) El peor caso 2) El caso promedio 3) El mejor … Continue reading «Análisis de Algoritmos | Conjunto 2 (peor, promedio y mejores casos)»
En la publicación anterior, discutimos el análisis de bucles . Muchos algoritmos son recursivos. Cuando los analizamos, obtenemos una relación de recurrencia para la complejidad del tiempo. Obtenemos el tiempo de ejecución en una entrada de tamaño n en función de n y el tiempo de ejecución en entradas de tamaños más pequeños. Por … Continue reading «Análisis de Algoritmo | Conjunto 4 (Resolución de recurrencias)»
Hemos discutido el análisis asintótico , los casos peor, promedio y mejor y las notaciones asintóticas en publicaciones anteriores. En este post, se discute un análisis de programas iterativos con ejemplos simples. 1) O(1): la complejidad de tiempo de una función (o conjunto de declaraciones) se considera como O(1) si no contiene bucle, recursividad ni … Continue reading «Análisis de Algoritmos | Conjunto 4 (Análisis de bucles)»
Stack es una estructura de datos lineal que sigue el orden LIFO (último en entrar, primero en salir), es decir, los datos se ingresan desde un extremo y mientras se eliminan, se eliminarán del mismo extremo. Las pocas operaciones más realizadas en una pila son: empujar() estallido() esta vacio() ojeada() Ahora comprobemos la eficiencia temporal … Continue reading «¿Cuál es la eficiencia de tiempo de las operaciones push(), pop(), isEmpty() y peek() de Stacks?»
Requisito previo : Completitud de NP, Clase de NP, Gráfico disperso , Conjunto independiente Problema: Dada la gráfica G = (V, E) y dos enteros a y b . Un conjunto de varios vértices de G tales que hay como máximo b aristas entre ellos se conoce como el subgrafo disperso del grafo G. Explicación: … Continue reading «Demostrar que Sparse Graph es NP-Complete»
Una array es una estructura de datos lineal. En una array, la operación para obtener un valor toma un tiempo constante, es decir, O(1). Veamos por qué es así. ¿Por qué la complejidad de obtener valor es O (1)? Como las arrays se asignan de forma contigua en la memoria, obtener un valor a través … Continue reading «¿Por qué el acceso a un elemento de Array lleva tiempo O(1)?»