Complejidad algoritmos

Universidad de Tarapacá

Alg. y Estructura de Datos

Análisis de complejidad de algoritmos
Eficiencia de algoritmos: Es la propiedad mediante la cual un algoritmo debe alcanzar la solución alproblema en el tiempo más corto posible y/o utilizando la cantidad más pequeña de recursos físicos. Un buen programador buscará el algoritmo más eficiente dentro del conjunto de aquellos que resuelvencon exactitud un problema dado. En la época en que los computadores eran caros y lentos era crítico el tema de la eficiencia de los algoritmos. Hoy que no existe esa limitante, la eficiencia siguesiendo un factor decisivo en el diseño de algoritmos. ¿Cómo medir la eficiencia de un algoritmo? A través de la técnica de análisis de algoritmos, que permite medir la dificultad inherente de un problema.El análisis de algoritmos se centra fundamentalmente en el análisis de los bucles. Notación O (o-grande) La notación O indica la cota superior del tiempo de un algoritmo, así en lugar de decir que unalgoritmo emplea un tiempo de 4n -1 en procesar un arreglo de largo n, se dirá que emplea un tiempo de O(n), que se lee “O grande de n” o “O de n” Así tendremos: O(1) orden constante O(log n) ordenlogarítmico O(n) orden lineal O(n log n) orden logarítmico O(n2) orden cuadrático 3 O(n ) orden cúbico a O(n ) orden polinomial (a > 2) n O(a ) orden exponencial (a > 2) O(n!) orden factorial Bucleslineales for (int i= 0; i < N; i++) { algo_de_O(1) }

Prof. Dianny Castro Ch.

Universidad de Tarapacá

Alg. y Estructura de Datos

Tendremos N * O(1) = O(n) Bucles logarítmicos A vecesaparecen bucles multiplicativos, donde la evolución de la variable de control no es lineal (como en los casos anteriores) c= 1; while (c < N) { algo_de_O(1) c = 2 * c; } El valor inicial de "c" es 1, siendo"2k" al cabo de "k" iteraciones. El número de iteraciones es tal que 2k >= N => k= EIS (log2 (N)) [EIS: Entero Inmediato Superior] y, por tanto, la complejidad del bucle es O(log n). Otro caso...