Eficiencia

Eficiencia ´Indice 1. Introducci´ on

2

2. La eficiencia de los algoritmos 2.1. Problemas y casos. Tama˜ no de los casos. . . . . . . . . . . . . . . . . . . . 2.2. Tiempo de ejecuci´on t(n). An´alisis de caso peor, caso mejor y caso medio. 2.3. Principio de invariancia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Orden asint´otico de una funci´on . . . . . . . . . . . . . . . . . . . 2.4. Notaciones O, Θ y Ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1. Notaci´on Θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2. Notaci´on O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.3. Notaci´on Ω . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5. Operaciones con ´ordenes de complejidad. Funciones an´onimas . . . . . . . 2.5.1. Funciones polin´omicas . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2. Usando l´ımites para calcular ´ordenes de complejidad . . . . . . . . 2.5.3. Suma y producto de ´ordenes de complejidad . . . . . . . . . . . . . 2.5.4. Funciones an´onimas . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

2 2 3 4 5 6 7 8 8 8 9 9 9 9

. . . . . . . . . .

10 10 11 11 12 12 12 13 13 13 14

. . . . . . . . . . .

14 15 15 16 17 17 17 18 18 18 20 20

3. An´ alisis de algoritmos 3.1. Operaciones elementales. . . . . . . . . . . . . . . . . . . 3.1.1. Modelos de computaci´on. . . . . . . . . . . . . . 3.2. Estructuras b´asicas de control . . . . . . . . . . . . . . . 3.2.1. Secuencia de instrucciones . . . . . . . . . . . . . 3.2.2. Sentencias condicionales tipo IF-THEN . . . . . . 3.2.3. Bucles FOR . . . . . . . . . . . . . . . . . . . . . 3.2.4. Instrucciones cr´ıticas . . . . . . . . . . . . . . . . 3.3. El caso especial de los algoritmos recursivos. . . . . . . . 3.3.1. Disminuci´on del tama˜ no del caso por divisi´on . . 3.3.2. Disminuci´on del tama˜ no del caso por sustracci´on 4. An´ alisis de los algoritmos de ordenaci´ on 4.1. Inserci´on directa . . . . . . . . . . . . . . 4.1.1. Movimientos . . . . . . . . . . . . 4.1.2. Comparaciones . . . . . . . . . . . 4.1.3. Conclusiones . . . . . . . . . . . . 4.2. Inserci´on binaria . . . . . . . . . . . . . . 4.2.1. Comparaciones . . . . . . . . . . . 4.3. Selecci´on directa . . . . . . . . . . . . . . 4.3.1. Comparaciones . . . . . . . . . . . 4.3.2. Movimientos . . . . . . . . . . . . 4.3.3. Conclusiones . . . . . . . . . . . . 4.4. Burbuja . . . . . . . . . . . . . . . . . . . 1

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . .

4.4.1. Comparaciones . . 4.4.2. Movimientos . . . 4.4.3. Conclusi´on . . . . 4.5. Quicksort . . . . . . . . . 4.5.1. Conclusi´on . . . . 4.6. Ordenaci´on por mont´ıculo 4.6.1. Conclusi´on . . . .

1.

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

21 21 21 21 23 23 24

Introducci´ on

Hemos visto en el cap´ıtulo anterior varios algoritmos de ordenaci´on. Ahora queremos reflexionar sobre la calidad de esos algoritmos. Hay varios sentidos en los que un algoritmo correcto puede ser mejor que otro. Entre las caracter´ısticas m´as valiosas de los algoritmos cabe destacar la claridad y la eficiencia. Pero la claridad es esencialmente cualitativa, y es dif´ıcil de medir. Eso no significa que no sea importante desde el punto de vista pr´actico: un programa dif´ıcil de entender, por m´as eficiente que sea, est´a abocado a causar problemas en el futuro. Y la verificaci´on de un algoritmo sencillo es m´as f´acil, lo que reduce el riesgo de errores en su ejecuci´on. La claridad, por otra parte, depende de forma inseparable de la documentaci´on del algoritmo. Volveremos en otro momento sobre ese tema, y en este cap´ıtulo nos vamos a centrar en la eficiencia. Las primeras secciones introducen los conceptos y la notaci´on propios del an´alisis de la eficiencia de los algoritmos. Para poner en pr´actica estos conceptos y notaciones vamos a aplicarlos en la u ´ltima secci´on al an´alisis de los algoritmos de ordenaci´on.

2. 2.1.

La eficiencia de los algoritmos Problemas y casos. Tama˜ no de los casos.

Los algoritmos que vamos a estudiar en este curso resuelven muchos casos distintos de un mismo problema. Cada caso concreto, en la jerga de la algoritmia, es un ejemplar del problema. Pero, por supuesto, seg´ un cual sea el caso que se considere, el algoritmo emplea m´as o menos tiempo, o consume m´as o menos espacio de memoria, etc. Cuando tenemos varios algoritmos disponibles para resolver un problema, debemos elegir cu´al de ellos es el mejor. El criterio que vamos a utilizar para seleccionar el mejor algoritmo se basa en el c´alculo de los recursos que el algoritmo emplea, seg´ un cu´al sea el caso que tenga que resolver. Los recursos a los que nos referimos son, primordialmente, los que hemos mencionado: el tiempo de proceso del algoritmo y el espacio en memoria que consume. Para poder hacer un an´alisis preciso de la calidad de los algoritmos necesitamos traducir estas ideas que hemos expuesto en expresiones cuantitativas, en n´ umeros, que podamos medir y calcular. El primer paso consiste en asignar a cada caso del problema un tama˜ no. Eso significa que tenemos que dar, para cada ejemplar o caso, un n´ umero, que sea representativo de la dificultad que para el algoritmo presenta resolver ese caso en particular. Ese n´ umero es lo que llamamos el tama˜ no de ese ejemplar. En algunos casos la elecci´on de la cantidad que hay que utilizar como tama˜ no del problema ser´a evidente. En otros, en cambio es necesario un an´alisis muy sutil para decidir cu´al es la medida correcta. En este curso, la mayor´ıa de los problemas ser´an de la primera clase: f´aciles. Adem´as, a medida que se gana en experiencia, las decisiones que al principio pueden parecer dif´ıciles se facilitan por el repertorio de ejemplos que vamos acumulando. Es esencial, por ejemplo, que todos los ejemplares de un mismo tama˜ no supongan un nivel de dificultad similar para el algoritmo, y que ese nivel de dificultad vaya aumentando con el tama˜ no, de manera que a mayor tama˜ no, mayor dificultad. Suponemos por tanto que, dado un ejemplar del problema que nos

2

interesa, vamos a ser capaces siempre de identificar ese ejemplar como un ejemplar de un cierto tama˜ no n.

2.2.

Tiempo de ejecuci´ on t(n). An´ alisis de caso peor, caso mejor y caso medio.

Para simplificar, vamos a centrar nuestra discusi´on inicial en el an´alisis comparativo del tiempo que tarda en ejecutarse un algoritmo. La discusi´on sobre la eficiencia en t´erminos de memoria es muy similar, y veremos ejemplos m´as adelante en el curso. Para fijar ideas supongamos que tenemos un algoritmo para resolver un problema, y a partir de ´el escribimos un programa de ordenador. Es decir, implementamos el algoritmo en un lenguaje de programaci´on concreto y en un ordenador concreto. A continuaci´on empezamos a utilizar el programa para resolver distintos ejemplares de ese problema. Es de suponer, si hemos usado una buena medida del tama˜ no del problema, que cuanto mayor sea el tama˜ no n del problema, m´as tardar´a el programa en ejecutarse. Llamaremos t(n) al tiempo que el programa tarda en ejecutarse en un ejemplar de tama˜ no n. Por supuesto hay una primera dificultad: puede que haya m´as de un ejemplar de tama˜ no n, y el tiempo para todos esos ejemplares no tiene porque coincidir. Para seguir adelante con la discusi´on, tenemos que tomar una decisi´on sobre qu´e es lo que necesitamos saber sobre el programa. 1. Lo m´as habitual es que nos preocupe saber cual es el tiempo m´aximo que el programa puede tardar en resolver el problema. Es decir, de entre todos los ejemplares de tama˜ no n escogemos aquel para el que el programa tarda m´as, y decimos que es el peor caso de tama˜ no n. Entonces tmax (n) significa el tiempo que se tarda para el peor caso. 2. Sin embargo a veces ese caso peor se presenta muy rara vez en la pr´actica, y en la mayor´ıa de los casos de tama˜ no n el programa tarda menos, incluso mucho menos. Ser´ıa u ´til saber ´esto a la hora de decidir si queremos usar el programa. As´ı que lo que podemos hacer es calcular el tiempo medio que el programa emplea en un ejemplar de tama˜ no n, y llamarlo tmed (n). Aunque este tiempo no tiene porque coincidir con el tiempo que emplea ning´ un ejemplar concreto, diremos que se tmed (n) es el tiempo del caso medio de tama˜ no n. Puesto que puede haber much´ısimos (en algunos casos infinitos) ejemplares de tama˜ no n, hacer esa media es complicado, y exige utilizar t´ecnicas de la teor´ıa de las probabilidades. 3. Finalmente, a veces tambi´en queremos saber cu´al es el tiempo m´ınimo que el programa va a tardar en resolver un ejemplar de tama˜ no n. En ese caso, el contrario del primero, debemos buscar el mejor caso de tama˜ no n, aquel para el que el programa tarda menos. Llamaremos tmin (n) al tiempo que se tarda en resolver el mejor caso de tama˜ no n. Correspondiendo a cada una de esas posibilidades se puede hacer un estudio del comportamiento del programa para distintos valores de n. En general, siempre nos preocupa como ser´a el comportamiento del programa cuando n sea grande. Como ya hemos dicho al describirlos, el an´alisis de caso medio es el m´as dif´ıcil de todos, porque hay que considerar todos los casos posibles y promediar sobre ellos. El an´alisis de caso mejor es m´as f´acil, pero s´olo nos da una estimaci´on optimista sobre el programa. Por esa raz´on, lo m´as frecuente es que al analizar un programa nuestro inter´es se centre en el tiempo tmax (n) del peor caso, que es comparativamente f´acil de obtener, y m´as u ´til si queremos saber c´omo de bueno es nuestro programa. Por esa raz´on, de ahora en adelante escribiremos a veces simplemente t(n) para referirnos de forma abreviada a tmax (n). Si nos referimos a alguno de los otros valores lo mencionaremos expl´ıcitamente.

3

2.3.

Principio de invariancia.

Nuestro objetivo en este cap´ıtulo es obtener herramientas para poder comparar dos algoritmos y decidir cu´al de los dos es mejor. Pero antes de llegar a comparar dos algoritmos, incluso cuando pensamos en un u ´nico algoritmo, todav´ıa tenemos que sortear alguna dificultad. Porque es evidente que para usar el algoritmo habr´a que traducirlo en un programa –en alg´ un lenguaje de programaci´on, tipo Pascal, C, Modula-2, etc.– y ejecutar ese programa en un ordenador concreto. Y claro, pensar´as, el programa no va a ser igual de r´apido en un ordenador de los a˜ nos ochenta que en una flamante m´aquina de u ´ltima generaci´on. Y por supuesto, el programa en Pascal, y el programa en C, aunque correspondan exactamente al mismo algoritmo, no tienen porque ser igual de r´apidos. Ni siquiera un mismo programa en Pascal, pero compilado con dos compiladores diferentes tiene que ser necesariamente igual de r´apido. As´ı que ¿qu´e importancia puede tener esa funci´on t(n) de la que hemos hablado, si depende del ordenador, del lenguaje de programaci´on y qui´en sabe de cu´antas cosas m´as? Hay que hilar m´as fino. Es innegable que t(n) depende de todas esas cosas. Pero ¿hasta qu´e punto? Supongamos que usas un ordenador A que es 10 veces m´as r´apido que el ordenador B. Entonces tA (n) ser´a 10 veces menor que tB (n). En general, el cambio de un modelo de ordenador a otro m´as r´apido, manteniendo todo lo dem´as igual, siempre significa que se tiene una relaci´on como ´esta: tA (n) = ctB (n) donde c es una constante que compara las velocidades de ambas m´aquinas. Cuando en lugar de cambiar de m´aquina lo que hacemos es cambiar de lenguaje de programaci´on, o de compilador dentro de un mismo lenguaje, ocurre algo muy parecido. Piensa por ejemplo en un compilador de C y uno de Pascal. Y escribe programas para un mismo algoritmo en ambos lenguajes. El compilador de Pascal puede ser muy r´apido haciendo unas cosas, y m´ as lento en otras. Pero si llamamos ahora tA (n) al tiempo que tarda el programa en Pascal y tB (n) al tiempo que tarda el programa en C, siempre se puede encontrar un par de constantes c1 y c2 tales que: c1 tA (n) ≤ tB (n) ≤ c2 tA (n) y esas constantes no dependen del tama˜ no n del caso. ¿Qu´e significa ´esto? Piensa por ejemplo que c2 = 2. Eso significa que tB (n) ≤ 2tA (n) Es decir, el programa en C (que tarda tB (n)) nunca tarda m´as del doble de lo que tarda el programa en Pascal. En definitiva, en este ejemplo, esto garantiza que usar C s´ olo puede provocar que nuestro programa tarde el doble. Te estar´as preguntado: “¿S´olo el doble?¿Y te parece poco?”. Volveremos en seguida sobre eso. Y si por ejemplo c1 = 31 , entonces 1 tA (n) ≤ tB (n) que es lo mismo que decir tA (n) ≤ 3tB (n) 3 Y eso significa que el programa en Pascal (que tarda tA (n)) nunca tarda m´as del triple de lo que tarda el programa en C. As´ı que lo peor que puede pasar si usamos Pascal es que nuestro programa tarde tres veces m´as. Lo importante de la anterior discusi´on es: 1. que cuando se compara el tiempo que se tarda empleando dos lenguajes distintos, o dos compiladores de un mismo lenguaje, etc., en definitiva, cuando se comparan dos implementaciones distintas A y B de un mismo algoritmo, siempre resulta que se llega a ecuaciones de la forma: c1 tA (n) ≤ tB (n) ≤ c2 tA (n) 4

2. una ecuaci´on como esa significa que al cambiar una implementaci´on por otra, el tiempo que tarda el algoritmo puede verse multiplicado por una constante que no depende del tama˜ no del caso. En definitiva, sabemos de antemano que al cambiar de implementaci´ on lo peor que puede pasar es que tengamos que esperar 2,3, 10 veces m´as, o en general c veces m´as. La primera de estas dos afirmaciones se suele llamar principio de invariancia, y no es una ley de la naturaleza, ni un teorema, ni nada parecido. Simplemente describe la situaci´on que se viene observando tras unas d´ecadas de experiencia en la programaci´on con diferentes m´aquinas y lenguajes de programaci´on. 2.3.1.

Orden asint´ otico de una funci´ on

Vuelvo sobre la pregunta que hemos dejado pendiente en el p´arrafo anterior: ¿te parece poco tardar el doble? Esta inocente pregunta es la clave para que podamos empezar a entender la idea clave al comparar dos algoritmos. Imag´ınate que tienes dos algoritmos para resolver un mismo problema. Y a partir de ellos produces dos programas, en el mismo lenguaje de programaci´ on y los ejecutas en el mismo ordenador. Imag´ınate adem´as que, en esas condiciones, el primer programa tarde: t1 (n) = 100n segundos para un caso de tama˜ no n, mientras que el segundo programa tarde t2 (n) = n2 segundos para un caso de tama˜ no n. ¿Qu´e algoritmo es mejor? Claro, para los primeros valores de n tales como 1, 2, 3, . . . se obtiene t2 (n) < t1 (n) De hecho en esos valores t1 es muchas veces mayor que t2 . Y si tuvi´eramos la garant´ıa de que s´olo vamos a necesitar resolver problemas de esos tama˜ nos peque˜ nos, sin duda preferir´ıamos el programa 2. Pero muy a menudo sucede que terminamos necesitando casos con valores de n mucho mayores. Fig´ urate por ejemplo que alguna vez necesitamos resolver un caso de tama˜ no n = 1000. Entonces: t2 (1000) = 10002 = 1000000 mientras que t1 (n) = 100 · 1000 = 100000 Ahora resulta que el programa t1 es 10 veces m´as r´apido que el t2 . Y si necesitas resolver un problema de tama˜ no 10000, la diferencia es a´ un m´as escandalosa: t2 (10000) = 100002 = 108 mientras que t1 (n) = 100 · 10000 = 106 Ahora t1 es 100 veces m´as r´apido que t2 . Algunos experimentos m´as con estas f´ormulas deber´ıan bastar para convencerte de que, para valores grandes de n, no s´olo es que t1 sea menor que t2 . Es que la magnitud de ambos n´ umeros crece de distinta forma. No podemos decir, por ejemplo, que t1 es siempre diez o cien veces m´as peque˜ no que t2 . No es “tantas veces m´as peque˜ no”, porque no son cantidades proporcionales. Sus o ´rdenes de magnitud son diferentes. El orden de magnitud de una funci´on es un concepto bien definido en matem´aticas (en particular en el an´alisis), al que aqu´ı s´ olo necesitamos acercarnos superficialmente. Hemos decidido por tanto elegir como mejor a aquel algoritmo que tarde menos en ejecutarse para ejemplares de un cierto tama˜ no n. Si tenemos dos algoritmos que resuelven el mismo problema y llamamos t1 (n), t2 (n) al tiempo que cada uno de los algoritmos emplea para resolver un caso (el peor caso, recu´erdalo) de tama˜ no n, est´a claro que si: t1 (n) ≤ t2 (n) para todo n entonces el algoritmo 1 es m´as r´apido que el dos sea cual sea el tama˜ no del caso, y por tanto debemos preferirlo siempre. 5

El punto de vista asint´ otico A veces las cosas no son tan sencillas. Puede ocurrir, por ejemplo, que t1 (n) sea m´as peque˜ no que t2 (n) para algunos valores, y m´as grande para otros. Si fuera muy dif´ıcil distinguir unos casos de otros, la comparaci´on de algoritmos resultar´ıa extremadamente complicada. Afortunadamente lo m´as frecuente es que suceda ´esto: existe un cierto valor N , tal que, a partir de ese valor (es decir para todos los n con n > N ), se cumple t1 (n) ≤ t2 (n) (o viceversa), como en esta figura:

En ese caso, decimos que t1 es asint´ oticamente menor que t2 . Como ya hemos dicho, al aumentar n, el tama˜ no del caso, aumenta su dificultad. Lo que significa que normalmente estamos especialmente interesados en los casos de tama˜ no grande. Un algoritmo que es m´as r´apido en los casos grandes (y dif´ıciles) es muchas veces preferible, incluso aunque no resulte demasiado bueno en casos peque˜ nos. Un comentario: cuando empleamos el punto de vista asint´otico, no nos preocupa encontrar el menor N a partir del cual t1 (n) ≤ t2 (n). Basta con establecer que hay un N a partir del cual se cumple esa desigualdad.

2.4.

Notaciones O, Θ y Ω

Vamos a establecer una cierta escala de eficiencia de los algoritmos basada en las ideas anteriores. Y lo primero que necesitamos es una forma de decir el lugar que un algoritmo ocupa en esa escala. Para hacer esto vamos a utilizar la funci´on t(n) que indica el tiempo (m´ınimo, m´aximo o promedio, eso habr´a que aclararlo en cada caso) que el algoritmo emplea en resolver un ejemplar de tama˜ no n. Vamos a estudiar como se comporta t(n) asint´oticamente, es decir, para valores de n grandes. En principio, la f´ormula concreta para t(n) puede ser muy complicada, depender de muchos detalles de la implementaci´on, etc´etera. Pero desde el punto de vista asint´otico, la mayor´ıa de esos detalles son irrelevantes. Cuando se aplica este punto de vista, la f´ormula para t(n) habitualmente se simplifica mucho. Ejemplo 2.1. Si por ejemplo tenemos un algoritmo A1 que cumple t1 (n) = n3 y hemos inventado un nuevo algoritmo A2 para el mismo problema que cumple: t2 (n) =

n4 + 4n3 + 2n + 1 n2 + 3n − 2 6

puede parecer dif´ıcil saber c´ omo de bueno es A2 comparado con A1 . Lo que tenemos que hacer es pensar asint´ oticamente. Cuando n es muy grande, el t´ermino m´ as importante en el numerador de la f´ ormula para t2 (n) es n4 . Y el t´ermino m´ as importante del denominador es n2 . Eso significa que para un n grande n4 t2 (n) ≈ 2 = n2 n Y por tanto el algoritmo A2 es mucho mejor que el A1 , en ese sentido asint´ otico, para valores de n suficientemente grandes. Lo que queremos hacer por tanto es evitar los detalles que oscurecen la comprensi´on de la f´ormula para t(n). De hecho, queremos ir un paso m´as all´a de lo que hemos hecho en este ejemplo. No vamos a tratar de encontrar la f´ormula exacta para t(n) para luego simplificarla asint´oticamente, eliminando los detalles que la complican. No, de hecho lo que vamos a hacer es tratar de obtener la f´ormula ya simplificada, eliminando los detalles durante el propio an´alisis del algoritmo. 2.4.1.

Notaci´ on Θ

En cualquier caso, queremos desarrollar una notaci´on para resumir el resultado final de esos an´alisis simplificadores. Una notaci´on con la que podamos decir algo como: “asint´oticamente, la f´ormula (complicada) t(n) se comporta como la f´ormula (mucho m´as sencilla) f (n)”. La notaci´on que vamos a emplear para esto se basa en la siguiente definici´on. Definici´ on 2.2 (Orden Θ). El conjunto T heta(f (n)) est´ a formado por todas las funciones g(n) que asint´ oticamente est´ an acotadas, tanto superiormente como inferiormente, por m´ ultiplos constantes de f (n). M´ as precisamente, g(n) est´ a en Θ(f (n)) si existen constantes c1 , c2 tales que c1 f (n) ≤ g(n) ≤ c2 f (n) para todo n suficientemente grande La notaci´on habitual en matem´aticas para decir que g(n) est´a en el conjunto Θ(f (n)) ser´ıa g(n) ∈ Θ(f (n)). Pero, por razones que luego veremos, en el an´alisis de algoritmos se hace una excepci´on y en lugar de esto se escribe g(n) = Θ(f (n)). En lo que sigue vamos a medir la calidad de un algoritmo, usando la notaci´on anterior. En ese caso la funci´on g(n) ser´a t(n), el tiempo (m´aximo, m´ınimo o promedio) que el algoritmo emplea en un caso de tama˜ no n. Mientras que f (n) debe ser alguna f´ormula sencilla que permita r´apidamente juzgar la calidad del algoritmo, compar´andolo con sus competidores. Las funciones f (n) m´as frecuentes son n, n2 y en general nk , junto con las funciones log n, n log n y en general nk log n. n2 − 3n est´ a en el conjunto Θ(f (n)) para 2 n2 f (n) = n2 o, como diremos m´ as a menudo, que − 3n = Θ(n2 ). Para ello, tenemos que 2 demostrar que hay dos n´ umeros c1 y c2 tales que: Ejemplo 2.3. Veamos por ejemplo que g(n) =

c1 n2 ≤

n2 − 3n ≤ c2 n2 2

si n es suficientemente grande. Dividiendo por n2 esto es: c1 ≤

1 1 − 3 ≤ c2 2 n

1 1 Y si tomamos por ejemplo c1 = , c2 = , entonces para n > 7 las desigualdades se cumplen. 14 2 Desde luego, existen otros valores de c1 y c2 que se podr´ıan haber usado, pero eso no es importante. Lo que importa es que exista alg´ un valor que sirva. 7

2.4.2.

Notaci´ on O

La notaci´on Θ que hemos visto nos obliga a acotar el comportamiento de las funciones tanto superior como inferiormente. En muchas ocasiones esto es demasiado complicado de hacer en un an´alisis asint´otico. Por ejemplo, puede ser f´acil estimar cu´anto va a tardar como mucho el algoritmo en resolver el peor ejemplar de tama˜ no n. Pero puede resultar muy dif´ıcil acotar inferiormente esa misma cantidad. No obstante, la cota superior sigue siendo una informaci´on muy valiosa sobre la calidad del algoritmo, y vamos a introducir una notaci´on para referirnos a ella. Definici´ on 2.4 (Orden O). El conjunto O(f (n)) est´ a formado por todas las funciones g(n) que asint´ oticamente est´ an acotadas superiormente por un m´ ultiplo constante de f (n). Es decir, g(n) est´ a en O(f (n)) si existe una constante c tal que g(n) ≤ cf (n) para todo n suficientemente grande Entonces, si tm´ax (n) es el tiempo que el algoritmo emplea en resolver el peor ejemplar de tama˜ no n, al decir que tm´ax (n) = O(f (n)), estamos acotando superiormente (salvo una constante) el tiempo que el algoritmo emplea para ese ejemplar, y en consecuencia tambi´en acotamos el tiempo que tarda para todos los ejemplares de tama˜ no n. Eso hace que la informaci´on tm´ax(n) = O(f (n)) sea especialmente valiosa: nos da una garant´ıa del rendimiento del algoritmo. En cambio, si sabemos que tm´ax (n) = Ω(f (n)), la estimaci´on que estamos obteniendo nos dice que el peor caso de tama˜ no n no tarda menos de una cierta cantidad. Pero puede haber otros ejemplares del mismo tama˜ no que tarden mucho menos, porque ´este es el peor. As´ı que esa informaci´on no es muy u ´til a la hora de predecir el comportamiento del algoritmo. 2.4.3.

Notaci´ on Ω

Para completar el repertorio de notaciones asint´oticas, introducimos la u ´ltima de las definiciones: Definici´ on 2.5 (Orden Ω). El conjunto Ω(f (n)) est´ a formado por todas las funciones g(n) que asint´ oticamente est´ an acotadas inferiormente por un m´ ultiplo constante de f (n). Es decir, g(n) est´ a en Ω(f (n)) si existe una constante c tal que cf (n) ≤ g(n) para todo n suficientemente grande La primera observaci´on evidente es que las tres notaciones est´an relacionadas as´ı: Teorema 2.6. Sean cuales sean f (n) y g(n), se cumple que g(n) = Θ(f (n)) si y s´ olo si g(n) = O(f (n)) y a la vez g(n) = Ω(f (n)). ´ Ordenes de complejidad Todas las funciones g(n) que cumplen g(n) = O(f (n)) se dice que son del orden de complejidad O(f (n)). Cuando sea g(n) = Θ(f (n)) diremos que g(n) es del orden de complejidad exacto Θ(f (n)).

2.5.

Operaciones con ´ ordenes de complejidad. Funciones an´ onimas

¿C´omo se demuestra, por ejemplo, que g(n) = Θ(f (n))? En principio siempre puede acudirse a la definici´on, y buscar las constantes c1 , c2 , etc´etera. Pero ´esto es demasiado detallado, y nos obligar´ıa a conocer con precisi´on la f´ormula de g(n). No es eso lo que queremos hacer. Ser´ıa bueno contar con m´etodos m´as c´omodos para aplicarlos durante el an´alisis de los algoritmos. Vamos a ver ahora algunas de las reglas que nos facilitan el trabajo: 8

2.5.1.

Funciones polin´ omicas

El orden de complejidad de cualquier polinomio viene determinado por su t´ermino de mayor grado: Teorema 2.7. Si g(n) = ak nk + an−1 k n−1 + · · · + a2 k 2 + a1 k + a0 entonces g(n) = Θ(nk ) 2.5.2.

Usando l´ımites para calcular ´ ordenes de complejidad

Teorema 2.8 (Regla del l´ımite). 1.

Si se cumple l´ım

n→∞

f (n) =0 g(n)

entonces f (n) = O(g(n)) 2.

Si se cumple l´ım

n→∞

f (n) = c 6= 0 g(n)

entonces f (n) = Θ(g(n)) 2.5.3.

Suma y producto de ´ ordenes de complejidad

Muchas veces obtenemos una f´ormula sumando o multiplicando otras f´ormulas. La siguientes herramientas son u ´tiles para esos casos: Teorema 2.9 (Regla de la suma). Si g1 (n) = Θ(f1 (n)) y g2 (n) = Θ(f2 (n)), entonces g1 (n) + g2 (n) = Θ (m´ax(f1 (n), f2 (n))) Esta regla es cierta si en lugar de Θ se usan ´ ordenes O o Ω Teorema 2.10 (Regla del producto). Si g1 (n) = Θ(f1 (n)) y g2 (n) = Θ(f2 (n)), entonces g1 (n) · g2 (n) = Θ (f1 (n) · f2 (n)) Esta regla es cierta si en lugar de Θ se usan ´ ordenes O o Ω 2.5.4.

Funciones an´ onimas

Ya sabemos que una igualdad como g(n) = Θ(f (n)) debe interpretarse como un s´ımbolo de pertenencia. Pero adem´as de este uso, la notaci´on asint´otica tambi´en se emplea en ecuaciones como en n2 + 3n − 1 = n2 + Θ(n) ¿Qu´e significa la notaci´on asint´otica en este caso? Pues significa que existe una funci´on h(n) = 3n − 1, que es de orden Θ(n) y tal que n2 + 3n − 1 = n2 + h(n). En general una ecuaci´on como g(n) = g˜(n) + Θ(f (n)) significa que existe una funci´on h(n) que es del order Θ(f (n)) y que se cumple g(n) = g˜(n) + h(n)

9

Este tipo de ecuaciones se emplean normalmente para destacar que g˜(n) es la parte importante de la f´ormula g(n), la parte que determina su orden asint´otico. Y lo que queremos hacer es no preocuparnos de la otra parte, h(n). Queremos olvidarnos de los detalles y decir “esta parte h(n) est´a controlada en tama˜ no, y no es importante”. Por eso a la funci´on h(n) se la denomina funci´on an´onima: porque en realidad no nos interesa conocerla en detalle, s´olo saber controlar su orden asint´otico. La notaci´on de funciones an´onimas es especialmente u ´til para simplificar el an´alisis de los algoritmos cuando se combina con las reglas del producto y de la suma. En efecto, si tenemos dos igualdades: g1 (n) = g˜1 (n) + O(f1 (n)) g2 (n) = g˜2 (n) + O(f2 (n)) Entonces se tiene: g1 (n) + g2 (n) = (˜ g1 (n) + g˜2 (n)) + O(m´ax(f1 (n), f2 (n))) Lo cual nos permite obtener una descripci´on de g1 (n) + g2 (n) sin tener que preocuparnos de los detalles de ambas f´ormulas. Veamos un ejemplo, usando en este caso la regla del producto: Ejemplo 2.11. Supongamos que es: g1 (n) = n3 + O(n2 ) g2 (n) = n5 + O(n4 ) Entonces g1 (n)g2 (n) = (n3 + O(n2 ))(n5 + O(n4 )) = n8 + n3 O(n4 ) + n5 O(n2 ) + O(n2 )O(n4 ) Esta igualdad debe interpretarse como que todos los s´ımbolos O(nk ) representan a funciones an´ onimas del orden correspondiente. Pero entonces la regla del producto nos dice directamente que O(n2 )O(n6 ) = O(n8 ). Y es evidente que n3 = O(n3 ), as´ı que n3 O(n4 ) = O(n7 ). Por la misma raz´ on n5 O(n2 ) = O(n7 ). As´ı que tenemos: g1 (n)g2 (n) = n8 + O(n7 ) + O(n7 ) + O(n6 ) Ahora basta aplicar la regla de la suma para concluir que O(n7 )+O(n7 )+O(n6 ) = 0(n7 ). Porque al sumar se toma el m´ aximo, y asint´ oticamente est´ a claro que ese m´ aximo es O(n7 ); el lector puede pensar que es O(2n7 ), pero hay que recordar que en los ´ ordenes asint´ oticos las constantes multiplicativas son irrelevantes. La conclusi´ on es que: g1 (n)g2 (n) = n8 + O(n7 ) Y para obtener esta estimaci´ on no hemos necesitado preocuparnos de los detalles concretos de las f´ ormulas g1 (n) y g2 (n). Con un poco de pr´ actica todo este c´ alculo se hace a simple vista, y de esa forma el an´ alisis del orden de complejidad de un algoritmo gana mucho en agilidad.

3. 3.1.

An´ alisis de algoritmos Operaciones elementales.

Una operaci´on elemental de un algoritmo es una operaci´on cuyo tiempo de ejecuci´on se puede acotar por una constante que s´olo depende de la implementaci´on (la m´aquina que se usa, el lenguaje, el compilador, etc´etera.) Por lo tanto esa constante no depende del caso concreto al que se aplique el algoritmo, no depende de n. 10

Cuando una operaci´on no es elemental, porque el tiempo que se tarda en realizarla depende del caso concreto en el que estamos, la estrategia consiste en descomponer esa operaci´on en operaciones m´as sencillas, hasta llegar a operaciones elementales. Y despu´es calcular el tiempo que emplea el algoritmo, contando el n´ umero total de operaciones elementales que realiza. Si c es la constante que acota el tiempo que se tarda en una operaci´on elemental, y para resolver un cierto caso el algoritmo tiene que hacer k operaciones elementales, entonces el tiempo que tarda est´a acotado por kc. Si cambiamos la implementaci´on el valor de c puede cambiar, pero no el de k, as´ı que las cotas asint´oticas de eficiencia no se ven alteradas. De esa manera habremos conseguido nuestro objetivo de dar una medida de la calidad de un algoritmo que no dependa de la implementaci´on. Como se ve el an´alisis de la eficiencia de un algoritmo sigue un curso similar al de su dise˜ no, con una estrategia de refinamiento que descompone acciones m´as complejas en acciones m´ as sencillas, hasta llegar al nivel de las operaciones elementales. 3.1.1.

Modelos de computaci´ on.

Otra observaci´on pertinente en este momento es que, para que el an´alisis de la eficiencia de los algoritmos quede bien definido, es absolutamente necesario dejar claro cu´ales son las operaciones que pueden considerarse elementales. Hacer eso es lo que se conoce como definir un modelo de computaci´ on. Y lo primero que hay que saber es que no hay un modelo de computaci´on u ´nico. El modelo de computaci´on describe, sin entrar en demasiados detalles, la arquitectura del hardware que se va a emplear en la implementaci´on del algoritmo. Y por ejemplo, si se emplean ordenadores con m´as de un procesador, en los que se pueden realizar varias operaciones simult´aneamente, entonces el repertorio de operaciones que se consideran elementales cambia. De la misma forma, si alguna vez llegan a estar disponibles los ordenadores cu´anticos, su juego de operaciones elementales ser´a radicalmente diferente en algunos aspectos del que ahora resulta habitual. y ya hay algoritmos dise˜ nados a la espera de esos ordenadores cu´anticos, que calculan su eficiencia teniendo en cuenta las operaciones que ser´ıan posibles con ellos. El modelo que nosotros vamos a emplear en este curso se ajusta en l´ınea generales a la arquitectura de las m´aquinas que casi todos conocemos y tenemos en casa: m´aquinas con un s´olo procesador, que siguen la arquitectura de Von Neumann. En este modelo vamos a considerar como operaciones elementales (al menos) las siguientes: operaciones de asignaci´on, de entrada/salida, o aritm´eticas mientras se lleven a cabo con tipos elementales de datos (enteros, reales, booleanos en el sentido habitual en los lenguajes de programaci´on). Estas mismas operaciones no pueden considerarse elementales si involucran tipos estructurados (matrices, registros, listas, ´arboles, grafos y el resto de tipos que veremos en temas posteriores) o si el tama˜ no de los datos obliga a representarlos usando estructuras que exceden del tama˜ no previsto en los tipos b´asicos. Por ejemplo, un entero de un mill´on de cifras no puede representarse con el tipo INTEGER de un lenguaje como Pascal, o Modula-2.

3.2.

Estructuras b´ asicas de control

Nuestro programas utilizan siempre una serie de estructuras de control b´asicas: sentencias condicionales tipo IF-THEN, bucle FOR o WHILE. Vamos a ver brevemente como se debe enfocar el an´alisis de la eficiencia a partir de un estudio de estas estructuras. Debe quedar claro que no se pueden dar reglas mec´anicas para este an´alisis, y que ser´a la experiencia, adquirida lo largo de los ejemplos que vamos a ver en todo el curso, la que permita llevar a cabo un an´alisis correcto. Aqu´ı se trata s´olo de presentar las ideas b´asicas, que iremos refinando poco a poco.

11

3.2.1.

Secuencia de instrucciones

Cuando tenemos una lista de instrucciones en nuestro programa que se ejecutan una tras otra, el tiempo de ejecuci´on total es simplemente la suma de los tiempos de cada una de ellas. 3.2.2.

Sentencias condicionales tipo IF-THEN

. La ejecuci´on de una de estas sentencias, tal como IF A THEN B ELSE C END supone: 1. Evaluar la sentencia A. Supongamos que esto lleva un tiempo tA (n), que puede depender del tama˜ no n del caso concreto del algoritmo. 2. Seg´ un A sea cierto o falso, evaluar B o C. Llamemos tB (n) y tc (n) a los tiepos que se tarda en evaluar estas sentencias seg´ un el tama˜ no del caso de que se trate. Entonces est´a claro que el tiempo total de evaluaci´on de la sentencia condicional est´a acotado por tA (n) + m´ax(tB (n), tC (n)) o, m´as sencillamente, por: m´ax(tA (n), tB (n), tC (n)) 3.2.3.

Bucles FOR

Queremos analizar el tiempo que emplea el algoritmo en bucles similares a ´este: FOR i : = 1 TO m DO P( i ) END donde P (i) representa el grupo de sentencias que forman el cuerpo del bucle. El caso m´ as f´acil de todos es aquel en el que el tiempo que se tarda en ejecutar P (i) no depende en realidad de i, incluso aunque dependa de n, el tama˜ no el caso de inter´es. En ese caso, y siempre que sea m ≥ 1, si el tiempo que se tarda en ejecutar P (i) es t(n), el tiempo total de ejecuci´on del bucle ser´a mt(n). Es importante entender que en general este bucle aparecer´a como parte dentro de un algoritmo m´as complejo. En esos casos, el valor del par´ametro m puede depender de cual sea el caso que se est´e tratando. As´ı que en general tenemos que escribir m(n)t(n) incluso cuando el tiempo de P (i) no depende de n. Por otra parte, puede ocurrir que el valor m = 0 (o alg´ un otro valor que 1)aparezca muchas veces a lo largo de la ejecuci´on. Cuando m < 1 el cuerpo del bucle no se ejecuta, pero eso no significa que el tiempo de ejecuci´on del bucle sea 0, porque el algoritmo tiene que comparar m con 1 y eso cuesta un cierto tiempo. Por otra parte los casos en los que el tiempo que tarda P (i) en ejecutarse dependen de i son m´as complicados, porque para obtener el tiempo que tarda en completarse el bucle debemos calcular y sumar los tiempos que emplea cada una de las iteraciones. Estas sumas pueden ser muy complicadas. Veremos m´as abajo algunos ejemplos. 12

Bucles WHILE El an´alisis de un bucle WHILE tal como ´este: WHILE A DO B END repite las consideraciones que ya hemos tratado en el caso de los bucles FOR (y lo mismo ocurre con otro tipo de bucles, tipo REPEAT-UNTIL, SWITCH, etc.) El an´alisis puede ser moderadamente sencillo si el cuerpo B del bucle no depende de la condici´on A. Pero en general el an´alisis de estos bucles es la parte m´as dif´ıcil de nuestro trabajo. Como hemos dicho antes, en lugar de tratar de dar reglas generales precisas, preferimos trabajar a partir de ejemplos. Otra estrategia para el an´alisis de la complejidad de un algoritmo iterativo es expresarlo de forma recursiva, con t´ecnicas como las que se han visto en la asignatura Programaci´on II. Y entonces llevar a cabo un an´alisis como el que veremos m´as abajo para los algoritmos recursivos. No obstante ´esto, debe tenerse en cuenta que el an´alisis de algoritmos recursivos que se aprende en Programaci´on II s´olo cubre los casos m´as sencillos de la recursividad. La transformaci´on de un algoritmo iterativo en recursivo nos puede conducir a esquemas recursivos mucho m´as complejos que los que all´ı se estudiaron, de manera que el esfuerzo de la transformaci´on haya sido in´ util. 3.2.4.

Instrucciones cr´ıticas

Una instrucci´on cr´ıtica de un algoritmo es una instrucci´on elemental que se ejecuta m´as veces dentro del algoritmo que ninguna otra. Si existe una instrucci´on cr´ıtica y podemos localizarla, entonces el an´alisis del algoritmo se simplifica, porque basta con contar el n´ umero de veces que se ejecuta esa instrucci´on para tener el orden exacto de complejidad del algoritmo. Pero es posible que no exista tal instrucci´on.

3.3.

El caso especial de los algoritmos recursivos.

Los algoritmos recursivos se han visto ya en la asignatura Programaci´on II. Nosotros trataremos con ellos, ampliando lo que se aprendi´o entonces, cuando veamos nuevos ejemplos de algoritmos recursivos. Aqu´ı nos limitaremos a recordar lo que se aprendi´o en esa asignatura en cuanto a la eficiencia de estos algoritmos. 3.3.1.

Disminuci´ on del tama˜ no del caso por divisi´ on

Teorema 3.1. Si el tiempo t(n) que el algoritmo emplea en resolver un ejemplar de tama˜ no n sigue una ecuaci´ on recurrente de la forma: ( cnk si 0 ≤ n < b t(n) = k at(n − b) + cn si n ≥ b entonces se tiene:

( Θ(nk+1 ) t(n) = Θ(an div b )

si a = 1 si a > 1

La relaci´on de recurrencia en este caso significa que al tratar de resolver un problema de tama˜ no n el algoritmo: 1. hace a llamadas recursivas 2. esas llamadas recursivas son problemas iguales, pero de tama˜ no n − b 3. Las operaciones auxiliares que se hacen en un problema de tama˜ no n ocupan un tiempo cnk Ese es el significado de los par´ametros a, b, k que aparecen en este algoritmo. 13

3.3.2.

Disminuci´ on del tama˜ no del caso por sustracci´ on

Teorema 3.2. Si el tiempo t(n) que el algoritmo emplea en resolver un ejemplar de tama˜ no n sigue una ecuaci´ on recurrente de la forma: ( cnk si 1 ≤ n < b t(n) = k at(n/b) + cn si n ≥ b entonces se tiene:

 k  Θ(n ) t(n) = Θ(nk log n)   Θ(nlogb a )

si a < bk si a = bk si a > bk

La relaci´on de recurrencia en este caso significa que al tratar de resolver un problema de tama˜ no n el algoritmo: 1. hace a llamadas recursivas 2. esas llamadas recursivas son problemas iguales, pero de tama˜ no n − b 3. Las operaciones auxiliares que se hacen en un problema de tama˜ no n ocupan un tiempo cnk Ese es el significado de los par´ametros a, b, k que aparecen en este algoritmo.

4.

An´ alisis de los algoritmos de ordenaci´ on

Vamos a utilizar los algoritmos de ordenaci´on que hemos visto en el tema anterior como ejemplos de la forma en que se realiza el an´alisis de la eficiencia de los algoritmos. Como hemos visto, se trata esencialmente de contar el n´ umero de operaciones elementales que lleva a cabo el algoritmo. Estos algoritmos ordenan el vector mediate dos operaciones: 1. comparaciones entre los elementos, que suponen evaluar una desigualdad como ´esta: a[i] < a[j] 2. y movimientos, que se traducen en asignaciones: x := a[i] Si el vector es un vector de enteros (tipo INTEGER), ambas operaciones se pueden considerar elementales. Pero esto no es cierto si los elementos del vector son de otro tipo, por ejemplo cadenas de caracteres que se desean ordenar alfab´eticamente. En cualquier caso, las comparaciones y movimientos son las operaciones b´asicas de estos algoritmos y aunque no sean elementales, se puede suponer que un movimiento supone hacer un cierto n´ umero fijo c1 de operaciones elementales, y una comparaci´on supone un n´ umero c2 de operaciones elementales. En general, ocurre que el coste de los movimientos supera al de las comparaciones. Es decir, que c1 > c2 . Resumiendo, si C es el n´ umero de comparaciones que realiza el algoritmo, M el de movimientos, y A el de operaciones elementales auxiliares, el total de operaciones elementales del algoritmo de ordenaci´on es: c1 M + c2 C + A 14

En general, el coste en tiempo que suponen las operaciones auxiliares es muy inferior al de los movimientos y comparaciones. As´ı que lo que vamos a hacer para cada uno de los algoritmos es contar, aproximadamente (con un punto de vista asint´otico), cu´antos movimientos y cu´antas comparaciones realiza el algoritmo para un ejemplar de tama˜ no n. Adem´as debemos hacer este recuento para el peor caso de tama˜ no n, para el mejor y adem´as hacer un promedio para todos los casos de tama˜ no n.

4.1.

Inserci´ on directa

Recordemos el pseudoc´odigo:

Procedimiento Ordenaci´on Por Inserci´on(A:vector[0..n] de enteros); para i:=2 hasta n hacer a[0]:=a[ i ]; j:=i−1; mientras a[0]
Movimientos

Mejor caso: Es f´acil ver que se produce cuando el vector inicialmente ya est´a ordenado. En este caso, en cada iteraci´on el algoritmo se limita a colocar el elemento a[i], que queremos ordenar entre los i − 1 primeros, en la posici´on 0 del centinela. El bucle mientras no se ejecuta nunca, porque los elementos que comparamos son siempre menores que el centinela. As´ı que al salir del bucle j + 1 sigue siendo i, y se lleva a cabo un segundo movimiento para colocar el centinela en la posici´on i. En total, dos movimientos por iteraci´on y n − 1 iteraciones, supone que el n´ umero de movimientos del mejor caso es: Mm´ın = 2(n − 1) Peor caso: Este caso ocurre cuando inicialmente el vector est´a ordenado en sentido contrario. Porque entonces, tras mover a[i] a la posici´on del centinela, se entra siempre en el bucle mientras, porque el centinela es menor que todos los elementos a[1], . . . , a[i − 1]. As´ı que hay que desplazarlos todos. En la primera iteraci´on del bucle para eso supone mover a la derecha el primer elemento del vector. En la segunda iteraci´on hay que mover dos elementos. En la tercera, tres, etc´etera, hasta que en la u ´ltima movemos n − 1 elementos. Y despu´es de cada iteraci´on hay que mover el centinela al hueco que hemos creado. As´ı que el total de movimientos se obtiene sumando los de cada iteraci´on. La siguiente tabla muestra el n´ umero de movimientos:

15

iteraci´on i 2 3 4 .. .

mover centinela 1 1 1 .. .

mover elementos de 1 a i − 1 1 2 3 .. .

mover centinela 1 1 1 .. .

n Total

1 n−1

n−1 1 + 2 + · · · + (n − 1)

1 n−1

Y finalmente el n´ umero total de movimientos es: Mm´ax = (n − 1) +

n−1 X

k + (n − 1) = 2(n − 1) +

k=1

n2 + 3n − 4 n(n + 1) = 2 2

La suma 1 + 2 + · · · + (n − 1) se lleva a cabo observando que el primer y u ´ltimo t´ermino suman n, que el segundo y pen´ ultimo tambi´en suman n, y as´ı sucesivamente; as´ı que tenemos (n − 1)/2 parejas que suman n. Este truco funciona en general para cualquier suma de una progresi´on aritm´etica. Aunque en este caso hemos hecho una cuenta completa del n´ umero de movimientos, no siempre ser´a posible tanto detalle. Eso en cualquier caso, no es relevante, en tanto seamos capaces de obtener el t´ermino que asint´oticamente es m´as importante. Promedio: El an´alisis del caso promedio siempre es el m´as complicado. Tenemos que pensar en todos los posibles vectores iniciales (hay infinitos) y suponer que todos son igualmente probables (lo cual puede no ser cierto en una aplicaci´on concreta del algoritmo, y habr´ıa que tenerlo en cuenta). En el caso de este algoritmo de inserci´on, los dos movimientos del centinela se efect´ uan siempre. Pero el movimiento del bucle mientras interior s´olo se produce si el centinela es menor que a[j]. La probabilidad de que un n´ umero entero sea menor que otro, cuando se escogen al azar, es 1/2. As´ı que, en promedio, en el bucle mientras se llevan a cabo la mitad de los movimientos que se har´ıan en el peor caso, cuando se hacen todos los posibles. Es decir: 1 n(n + 1) n2 + 9n − 10 Mmed = 2(n − 1) + = 2 2 4 4.1.2.

Comparaciones

El recuento de las comparaciones que se efect´ uan en este m´etodo es similar al que hemos hecho para los movimientos. Mejor caso: En el caso de un vector inicialmente ya ordenado, hacemos una sola comparaci´on por cada iteraci´on del bucle para, que nos impide entrar en el bucle mientras. As´ı que en este caso el n´ umero de comparaciones coincide con el de iteraciones Cm´ın = n − 1 Peor caso: Si el vector inicial est´a ordenado en sentido contrario, entonces entramos en el bucle mientras tantas veces como sea posible. Y cada vez que se entra en el bucle se eval´ ua la comparaci´on que lo controla. As´ı que por cada movimiento se efect´ ua una comparaci´on. Pero adem´as se efect´ ua una comparaci´on extra, con el centinela, que sirve para salir del bucle y que no conduce a ning´ un movimiento. La suma que hay que hacer es parecida a la que hicimos en el caso de los movimientos: Cm´ax = 2 + 3 + 4 + · · · + n = 16

(n − 1)(n + 2) n2 + n − 2 = 2 2

Promedio: Un razonamiento similar al que hicimos en el caso de los movimientos muestra que el n´ umero de comparaciones en promedio es la mitad de las que hicimos en el peor caso. Es decir: 1 n2 + n − 2 Cmed = Cm´ax = 2 4 4.1.3.

Conclusiones

Como ya hemos dicho, en general el peso de los movimientos supera al de las comparaciones en el recuento de operaciones elementales. As´ı que el t´ermino asint´oticamente dominante a la hora de calcular el tiempo empleado por el algoritmo de inserci´on es el de los movimientos. Ese tiempo es un m´ ultiplo constante del n´ umero de movimientos que realiza el algoritmo. A la vista de los anteriores resultados se deduce que para el algoritmo de inserci´on directa: tm´ın = Θ(n),

4.2.

tm´ax = Θ(n2 ),

tmed = Θ(n2 )

Inserci´ on binaria

La inserci´on binaria s´olo cambia la forma en la que se busca la posici´on de inserci´on, pero no afecta al n´ umero de movimientos. Es f´acil entender que no vamos a obtener una mejora en la calidad asint´otica del algoritmo, a pesar de que el tiempo de ejecuci´on ser´a sin duda mejor. Nos limitamos por tanto al recuento de comparaciones. 4.2.1.

Comparaciones

Para localizar la posici´on de inserci´on entre los i primeros tengo que hacer b´ usqueda binaria en un vector de i elementos. La b´ usqueda binaria tiene asint´oticamente un coste del orden dlog ie (ver el texto base de Programaci´on II, p´ag. 77; all´ı est´a b´ usqueda se llama dicot´omica). As´ı que para hacer todas las b´ usquedas que necesito tengo que hacer: dlog 2e + dlog 3e + · · · + dlog n − 1e Esta suma se puede aproximar bastante bien (en el caso del logaritmo) por la integral Z n log xdx = n(log n − log e) + log e 1

En cualquier caso, el n´ umero de comparaciones es del orden n log n, y asint´oticamente n log n  n2 lo cual demuestra que para la inserci´on binaria, el n´ umero de movimientos es, con mucho, el que determina la eficacia del algoritmo.

17

4.3.

Selecci´ on directa

Recordemos el pseudoc´odigo Procedimiento Ordenaci´ on por selecci´ on(VAR a:vector[1..n] de enteros); VAR PosMin, Min:entero; i,j,k:entero; para i desde 1 hasta n − 1 hacer {Buscamos el m´ınimo en las posiciones de la i a la n.} P osM in := i M in := a[P osM in] para j desde i + 1 hasta n hacer si a[j] < M in entonces P osM in := j M in := a[P osM in] fin si fin para {y ahora colocamos ese m´ınimo en la posici´on i} a[P osM in] := a[i]; a[i] := M in; fin para El algoritmo, para cada i de 1 a n busca el m´ınimo en las posiciones i a n y lo coloca en la posici´on i del vector. Como en el caso anterior, la clave del an´alisis de este algoritmo es un recuento del n´ umero de movimientos y comparaciones. 4.3.1.

Comparaciones

Las comparaciones se usan en este algoritmo para buscar, en el bucle para interno, el m´ınimo entre las posiciones de la i a la n. Y por eso es f´acil entender que el n´ umero de comparaciones no depende del vector inicial. En la primera iteraci´on del bucle interno hacemos n−1 comparaciones, en la siguiente n − 2, y as´ı sucesivamente, hasta que en la u ´ltima hacemos 1 comparaci´on C = (n − 1) + (n − 2) + · · · + 1 =

n2 − 2 2

Como hemos dicho, el n´ umero de comparaciones es el mismo en todos los casos. 4.3.2.

Movimientos

Los movimientos de este algoritmo que dependen del vector con el que trabajamos son los que quedan dentro de la sentencia condicional: si a[j] < M in entonces P osM in := j M in := a[P osM in] fin si Y el n´ umero de veces que se ejecuta el cuerpo de este condicional depende de la forma en que est´en ordenados los elementos de las posiciones finales del vector, de la i a la n. 18

Mejor caso: Es f´acil ver que el mejor caso de este algoritmo tambi´en aparece si el vector inicial ya est´a ordenado. Porque entonces al buscar el m´ınimo, lo localizamos en la primera posici´on, la i. Se entra una vez en el condicional, pero ya no se vuelve a entrar. Es decir, que en cada iteraci´on del bucle para externo se realizan tres movimientos: Mm´ın = 3(n − 1) Peor caso: Tambi´en ocurre cuando el vector inicial est´a ordenado en sentido contrario. En cada vuelta del bucle interno un elemento intercambia su posici´on con el sim´etrico, y ambos quedan ya ordenados. Pero hasta llegar al m´ınimo se guardan en la variable auxiliar todos los que encontramos. As´ı que en la primera iteraci´on,entramos en el condicional n−1 veces. En la siguiente iteraci´on, entramos no una, sino dos veces menos, es decir n − 3, porque ahora el u ´ltimo elemento del vector es el m´aximo y no se guarda en la variable auxiliar. En la siguiente iteraci´on se entra en el condicional n − 5 veces, y as´ı la zona de b´ usqueda va disminuyendo cada vez en dos, uno por cada extremo, hasta llegar al centro del vector. En ese momento el vector ya est´a ordenado y en las siguientes iteraciones no se entra en el condicional. La suma de movimientos dentro del condicional por lo tanto es la siguiente, suponiendo un n´ umero par de elementos: n2 (n − 1) + (n − 3) + · · · + 1= | {z } 4 n/2 t´erminos Puede comprobarse que el resultado es el mismo si el vector tiene una cantidad impar de elementos. A estos movimientos hay que sumarles los 3(n − 1) que se efect´ uan incondicionalmente, as´ı que n2 Mm´ax = 3(n − 1) + 4 Promedio: Atenci´ on: Este an´alisis es de una complejidad mayor que los anteriores, porque exige conocimientos de la teor´ıa de probabilidades y sobre la suma de la serie arm´onica. Tenemos que calcular el promedio de movimientos en el condicional. En la primera iteraci´on el condicional examina los elementos del 2 al n. Si el elemento a[2] nos hace entrar en el condicional (y hacer un movimiento) es porque es menor que el primero. La proba1 bilidad de que eso ocurra es . A continuaci´on, si el elemento a[3] nos hace entrar en el 2 condicional, es porque es menor que los dos que le preceden. Eso ocurre con probabilidad 1 . Y as´ı sucesivamente: la probabilidad de entrar en el condicional en el u ´ltimo elemento 3 1 es . En la siguiente iteraci´on la situaci´on es similar, pero empezamos a partir de a[3], y n as´ı sucesivamente, en cada iteraci´on vamos reduciendo la zona de b´ usqueda del m´ınimo. Ahora vamos a calcular el promedio del n´ umero de desplazamientos. Recordemos que en estad´ıstica el promedio es la esperanza de una variable aleatoria X. En nuestro caso la variable aleatoria es Mi , el n´ umero de movimientos en la iteraci´on n´ umero i del bucle externo. En esa iteraci´on buscamos en las posiciones de la i + 1 a la n, es decir en n − i posiciones. Llamemos Mi,j a una variable aleatoria que vale 1 o 0 seg´ un que hagamos o no un movimiento al llegar al elemento j en la iteraci´on i (con j rel="nofollow"> i). Obs´ervese que: Mi = Mi,i+1 + Mi,i+2 + · · · + Mi,n 19

La probabilidad de que Mi,j valga 1 (se ha hecho un movimiento) es, como hemos visto, 1 la de que a[j] sea el m´ınimo entre a[i], . . . , a[j]. Y esa probabilidad es . As´ı que j−i+1 el valor medio de Mi,j es:   1 1 1 = E(Mi,j ) = 1 · +0· 1− j−i+1 j−i+1 j−i+1 Recordemos que la esperanza de una variable aleatoria X que puede tomar los valores X1 , . . . , Xk con probabilidades respectivas p1 , . . . , pk es E(X) = p1 X1 + p2 X2 + · · · + pk Xk Por tanto: E(Mi ) = E(Mi,i+1 ) + E(Mi,i+2 ) + · · · + E(Mi,n ) =

1 1 1 + + ··· + = Hn−i − 1 2 3 n−i+1

siendo Hk los n´ umeros arm´onicos. Puesto que Hk ≈ ln k + γ siendo γ = 0,577216 . . . la constante de Euler, se puede aproximar E(Mi ) ≈ 1 + ln(n − i) + γ As´ı pues, el promedio del n´ umero total de movimientos es: Mmed = E(M ) = E(M1 )+E(M2 )+· · ·+E(Mn−1 ) = n(γ+1)+

n−1 X

log(n−k) ≈ n(log n+γ)

k=1

4.3.3.

Conclusiones

La complejidad temporal del algoritmo de selecci´on viene determinada, como en el caso de la inserci´on, por el n´ umero de movimientos y comparaciones. El n´ umero de comparaciones, en todos los casos, es cuadr´atico en n, porque no depende del orden inicial del vector. As´ı que tm´ın = Θ(n2 ),

tm´ax = Θ(n2 ),

tmed = Θ(n2 )

para este algoritmo. Sin embargo, la virtud de este algoritmo est´a en el bajo n´ umero de movimientos que se efect´ uan en promedio, del orden n log n como hemos visto. Eso significa que, entre los algoritmos elementales, este suele ser el preferido para ordenar un vector.

4.4.

Burbuja

Este algoritmo procede iterativamente tratando de hundir sucesivamente cada elemento del vector, de manera que en cada iteraci´on se a˜ nade un elemento a la parte final, ya ordenada del vector. El pseudoc´odigo es: Algoritmo: Ordenaci´ on por el m´ etodo de la burbuja: para i desde n bajando hasta 2 hacer para j desde 1 hasta i − 1 hacer si a[j] > a[j + 1] entonces Intercambiar a[j] y a[j + 1] fin si fin para fin para T´engase en cuenta que cada intercambio supone 3 movimientos. Analicemos el n´ umero de movimientos y comparaciones. 20

4.4.1.

Comparaciones

La u ´nica comparaci´on del algoritmo es la que aparece en la sentencia si. Es evidente que el n´ umero de comparaciones no depende del vector inicial, porque la condici´on de esa sentencia se eval´ ua una vez en cada iteraci´on. As´ı que el n´ umero de comparaciones coincide con el de iteraciones, y es: n2 − n C = 1 + 2 + · · · + (n − 1) = 2 Esto indica que, independientemente de lo que ocurra con los movimientos, el orden asint´otico de este algoritmo tambi´en va a estar en Θ(n2 ) en todos los casos: mejor, peor y promedio. 4.4.2.

Movimientos

Mejor caso: Si el vector ya est´a ordenado, no hay movimientos. Mm´ın = 0 Peor caso: Cuando el vector inicialmente est´a ordenado en sentido contrario, entonces cada comparaci´on produce un intercambio, con tres movimientos implicados. As´ı pues: Mm´ax = 3C= 3

n2 − n 2

Promedio: Cada vez que hacemos una comparaci´on la probabilidad de que haya que hacer un intercambio es 1/2. As´ı que la mitad de las veces habr´a que hacerlo, y se deduce que el n´ umero promedio de movimientos es la mitad del n´ umero m´aximo. As´ı que 1 n2 − n Mmed = Mm´ax = 3 2 4 4.4.3.

Conclusi´ on

El m´etodo de la burbuja no ofrece mejoras significativas con respecto a los otros m´etodos que hemos visto, especialmente cuando se le compara con la ordenaci´on por selecci´on. S´olo tiene sentido emplearlo en el caso de vectores que inicialmente ya est´an pr´acticamente ordenados. En esos casos el algoritmo utiliza un n´ umero peque˜ no de movimientos para la ordenaci´on.

4.5.

Quicksort

El algoritmo Quicksort es un algoritmo recursivo, como los que se han visto en la asignatura Programaci´on II. Su pseudoc´odigo es: Quicksort(VARv[1..n], p, q) si p < q entonces r :=Partici´on(v, p, q) Quicksort(v, p, r − 1) Quicksort(v, r + 1, q) fin si Por tanto podemos tratar de aplicar el esquema que se vio all´ı para analizar la eficiencia de los algoritmos recursivos (ver la secci´on (3.3)). La f´ormula recursiva para t(n) es f´acil de obtener: el algoritmo parte un vector de longitud n en dos trozos, de longitudes que vamos a llamar i y

21

n − i − 1, y les aplica el algoritmo. El tiempo que lleva hacer la partici´on es un m´ ultiplo de n. Pongamos cn para una cierta constante. De esa forma: T (n) = T (i) + T (n − i − 1) + cn A partir de esta f´ormula se puede llevar a cabo el estudio del tiempo en el peor y mejor caso, y en promedio. Mejor caso: Este caso ocurre cuando el pivote que se elige tiene la propiedad de dividir siempre al vector en dos trozos de longitud n/2. Entonces la ecuaci´on recursiva se convierte en T (n) = 2T (n/2) + cn Y las f´ormulas para recurrencias producen directamente T (n) = Θ(n log n) Peor caso: Se presenta cuando el pivote es siempre el m´aximo o el m´ınimo en cada partici´on, de manera que una de las dos partes del vector queda vac´ıa. Entonces i = 0, n−i−1 = n−1, y la ecuaci´on recursiva queda: T (n) = T (n − 1) + cn La soluci´on es T (n) = Θ(n2 ). Promedio: En este caso todos los tama˜ nos posibles de la partici´on (es decir, todos los valores de i) son igualmente probables. La probabilidad de cada uno de ellos es 1/n, y el valor medio de T (i) (obs´ervese que T (n − i − 1) tiene que ser el mismo) es Pn−1 j=0

T (j)

n con lo que la ecuaci´on de recurrencia se convierte en: Pn−1 j=0 T (j) T (n) = 2 + cn n La dificultad en este caso est´a en que esta f´ormula no es ninguno de los dos casos que se han estudiado en Programaci´on II. As´ı que nos planteamos un estudio directo del problema. Multiplicando por n la relaci´on anterior: nT (n) = 2

n−1 X

T (j) + cn2

j=0

Si se escribe esto para n − 1 ser´a: (n − 1)T (n − 1) = 2

n−2 X

T (j) + c(n − 1)2

j=0

Y restando se tiene: nT (n) − (n − 1)T (n − 1) = 2T (n − 1) + 2cn − c De donde (despreciado el t´ermino constante): nT (n) = (n + 1)T (n − 1) + 2cn 22

As´ı que: T (n) T (n − 1) 2c = + n+1 n n+1 Y usando esta relaci´on para n, n − 1, . . . , 2 se llega a: n+1

X1 T (n) T (1) = + 2c n+1 2 i i=1

Por tanto T (n) = O(n log n) 4.5.1.

Conclusi´ on

El algoritmo Quicksort es uno de los algoritmos de ordenaci´on de vectores conocidos con mejor rendimiento en promedio. El orden n log n es muy ventajoso comparado con el n2 de los algoritmos elementales que hab´ıamos revisado. El inconveniente fundamental del Quicksort es que su peor caso es cuadr´atico. No obstante, el comportamiento promedio es el mejor entre todo los algoritmos de ordenaci´on de vectores in situ que vamos a ver.

4.6.

Ordenaci´ on por mont´ıculo

El an´alisis en el caso promedio de este algoritmo es complejo, as´ı que aqu´ı nos vamos a limitar dar una estimaci´on asint´otica del tiempo del peor caso de este algoritmo. Recordemos aqu´ı que este algoritmo tiene una descripci´on muy sencilla: procedimiento OrdenacionPorMonticulo(var T [1..n]); CrearMonticulo(T ); para k desde n bajando hasta 2; hacer Intercambiar T [1] y T [k]; Hundir(T [1..k − 1], 1); fin para Como puede verse, primero debemos contar el n´ umero de operaciones necesarias para crear un mont´ıculo. Despu´es hay un bucle para con n−1 iteraciones, en el que se realiza un intercambio (3 movimientos) y se llama al procedimiento Hundir, para hundir la ra´ız de un mont´ıculo de k − 1 elementos. Empecemos por analizar el procedimiento que crea un mont´ıculo a partir de un vector. Su c´odigo es: procedimiento CrearMont´ıculo(var T [1..n], i); para i := n ÷ 2 bajando hasta 1 hacer Hundir(T,i); fin para donde el procedimiento Hundir es

23

Procedimiento Hundir(var T [1..n], i); k:=i; repetir j := k; {buscamos el hijo mayor del nodo j} si 2j ≤ n y T [2j] > T [k]; entonces k := 2j; fin si si 2j < n y T [2j + 1] > T [k]; entonces k := 2j + 1; fin si intercambiar T [j] y T [k]; hasta que j=k;{en ese momento el nodo se ha hundido hasta su posici´on final} En cada repetici´on de este procedimiento Hundir se elige el m´aximo entre los dos hijos de un nodo y ese m´ınimo se compara con el nodo. Eso supone dos comparaciones en cada nodo. Y despu´es se produce un intercambio, que implica tres movimientos. Estas operaciones se repiten en cada nivel, hasta que a, lo sumo, se alcanza una hoja (aunque el proceso puede detenerse antes). Sabemos que el nodo a[k] est´a en el nivel blog kc y que las hojas est´an en el nivel blog nc o tal vez blog nc − 1 (si el ´arbol no est´a completo). Por lo tanto el n´ umero de comparaciones y movimientos que implica una llamada Hundir(T,k) es proporcional a (log n − log k) Y obs´ervese que hundir la ra´ız de un mont´ıculo de n nodos supone un n´ umero de operaciones proporcional a log n. Ahora es f´acil analizar el algoritmo de ordenaci´on por mont´ıculo. En la fase de creaci´on del mont´ıculo el procedimiento Hundir se ejecuta para cada nodo a[k] con k de 1 a n/2. Y en la segunda fase, aparte de un intercambio, se hunden las ra´ıces de mont´ıculos con un n´ umero de nodos que va desde n hasta 2. As´ı que el total de operaciones es proporcional a: X

k = 1n/2(log n − log k) +

n X

log j

j=2

Ambas sumas tienen menos de n t´erminos, y cada sumando en cada una de ellas es a lo sumo log n. As´ı que el total es menor que n log n. Eso significa que para la ordenaci´on por mont´ıculo se cumple: tm´ax (n) = Θ(n log n) 4.6.1.

Conclusi´ on

El algoritmo de ordenaci´on por mont´ıculo tiene un comportamiento promedio complicado de analizar, pero que es tambi´en de orden Θ(n log n). Sin embargo, el promedio de Quicksort es mejor. A cambio, la ordenaci´on por mont´ıculo tiene un caso peor mucho mejor que el de Quicksort. Esa homogeneidad de comportamiento, con un coste promedio similar al del caso peor, es la principal virtud de la ordenaci´on por mont´ıculo, cuando se precisa garantizar que la ordenaci´on no va a transcurrir de forma inesperadamente lenta en algunos casos.

24