Observe que en cada caso cuando el subíndice n está entre dos potencias de 2, n es 1 más que el exponente de la menor potencia de 2. En otras palab...

Observe que en cada caso cuando el subíndice n está entre dos potencias de 2, n es 1 más que el exponente de la menor potencia de 2. En otras palabras: Si 2i n 2i 1, entonces n i 1 11.5.1 Pero si 2i n 2i 1, entonces [por la propiedad (11.4.2) del ejemplo 11.4.1] i log2n . Sustituyendo en el enunciado (11.5.1) se infiere que n log2n 1. Ahora puede emplearse inducción matemática para demostrar la validez de la fórmula encontrada en el ejemplo 11.5.4. Ejemplo 11.5.5 Verificando la validez de la fórmula Use inducción matemática fuerte para demostrar que si 1, 2, 3, es una sucesión de números que satisface la relación de recurrencia y la condición inicial 1 1 y k 1 k 2 para todos los enteros k 1 entonces 1, 2, 3, satisface la fórmula wn = ⌊log2 n⌋ + 1 para todos los enteros n 1. Solución Sea 1, 2, 3, la sucesión definida al especificar que 1 1 y k 1 k 2 para todos los enteros k 2 y aceptemos que la propiedad P(n) sea la ecuación n log2 n 1 P n Usaremos inducción matemática para demostrar que para todos los enteros n 1, P(n) es verdadera. Demostración de que P(1) es verdadera: Por definición de 1, 2, 3, , tenemos que 1 1. Pero este también es el caso para log21 1 0 1 1. Así 1 log21 1 y P(1) es verdadera. 11.5 Aplicación: análisis de la eficiencia de un algoritmo II 771 Demostración de que para todos los enteros k 1, si P(i) es verdadera para todos los enteros i de 1 a k, entonces P(k 1) también es verdadera: Sea k cualquier entero con k 1 y supongamos que i log2 i 1 para todos los enteros i con 1 i k. hipótesis de inducción Debemos demostrar que k 1 log2 k 1 1 P k 1 Consideremos los dos casos: k es par y k es impar. Caso 1 (k es par): En este caso, k 1 es impar y k 1 1 k 1 2 1 k 2 1 log2 k 2 1 log2 k ฀ log2 2 2 log2 k ฀ 1 2 log2 k 1 2 log2 k 1 1 por definición de 1, 2, 3, . , porque k 1 2 k 2 ya que k 1 es impar, por hipótesis de inducción porque ya que k es par, k 2 y así 1 k 2 k 2 k sustituyendo en la identidad logb(x y) logb x ฀ logb y del teorema 7.2.1, porque log2 2 1, sustituyendo x log2 (k) en la identidad x ฀ 1 x ฀ 1 deducida en el ejercicio 15, sección 4.5, por la propiedad (11.4.3) del ejemplo 11.4.2. Caso 2(k es impar): En este caso, se puede demostrar que k log2 k 1. El análisis es muy similar al caso 1 y se deja como ejercicio 16 al final de la sección. Así, sin importar si k es par o k es impar, k 1 log2 k 1 1, que es lo que se quería demostrar. [Como los pasos básico e inductivo se han probado, entonces queda completa la demostración por inducción matemática fuerte.] El ejemplo final muestra cómo usar la fórmula para 1, 2, 3, . para encontrar un orden para el algoritmo, en el peor caso. Ejemplo 11.5.6 El algoritmo de búsqueda binaria es logarítmico Dado que por el ejemplo 11.5.5, para todos los enteros positivos n, n log2 n 1, demuestre que en el peor caso, el algoritmo de búsqueda binaria es (log2n). Solución Para cualquier entero n 2, n log2 n 1 log2 n n log2 n 1 log2 n n log2 n log2 n log2 n log2 n n 2 log2 n por el ejemplo 11.5.5, porque x x 1 y x x para todos los números reales x, puesto que el logaritmo en base 2 es creciente, si 2 n, entonces 1 log2 2 log2 n. 772 Capítulo 11 Análisis de la eficiencia de un algoritmo Tanto n como log2 n son positivos para n 2. Por tanto, log2 n n 2 log2 n para todos los enteros n 2. Sean A 1, B 2 y k 2. Entonces A log2 n n B log2 n para todos los enteros n k. Así que por definición de notación , n es (log2n). Pero n, el número de iteraciones del bucle while, es proporcional al número de comparaciones efectuadas al ejecutar el algoritmo de búsqueda binaria. Entonces el algoritmo de búsqueda binaria es (log2n). Los ejemplos del 11.5.2 al 11.5.6 muestran que en el peor caso, el algoritmo de búsqueda binaria tiene orden log2 n. Como se observó en la sección 11.3, en el peor caso el algoritmo de búsqueda sucesiva tiene orden n. Esta diferencia en eficiencia crece de manera importante conforme n aumenta. Suponiendo que una iteración del bucle se realiza cada nanosegundo, entonces al efectuar n iteraciones para n 100 000 000 requiere 0.1 segundos, mientras que el hacer log2 n iteraciones requiere 0.000000027 segundos. Para n 100 000 000 000 los tiempos son 1.67 minutos y 0.000000037 segundos, respectivamente. Y para n 100 000 000 000 000, los respectivos tiempos son 27.78 horas y 0.000000047 segundos. Ordenamiento por mezcla Observe que es mucho más fácil escribir un algoritmo detallado para búsqueda sucesiva que para búsqueda binaria. Pero ésta es mucho más eficiente que la búsqueda sucesiva. Dicha situación ocurre frecuentemente en ciencia de la computación. Comúnmente, la solución “obvia” a un problema es menos eficiente que una inteligente solución que es más complicada en su descripción. En el texto y en los ejercicios de la sección 11.3, dimos dos métodos para ordenamiento, por inserción y por selección, los cuales son formalizaciones de métodos que los seres humanos utilizan frecuentemente en situaciones ordinarias. ¿El enfoque de divide y vencerás puede emplearse para encontrar un método de ordenamiento más eficiente que esos? Resulta que la respuesta es un enfático “sí”. En efecto, en algunas de las décadas pasadas, los científicos computacionales han desarrollado varios métodos de ordenamiento basados en divide y vencerás, los cuales son más complejos de describir pero son significativamente más eficientes que el de inserción o que el de selección. Uno de esos métodos, ordenamiento por mezcla, se obtiene al pensar recursivamente. Imagine que ya se conoce una manera eficiente de ordenar arreglos de longitud menor que k. ¿Cómo se puede emplear dicho conocimiento para ordenar un arreglo de longitud k? Una manera es suponer que el arreglo de longitud k se divide en dos partes burdamente iguales y que cada parte es ordenada utilizando el método ya conocido. ¿Existe una manera eficiente de combinar las partes en un arreglo ordenado? Seguro. Sólo “mézclalos”. La figura 11.5.4 muestra cómo trabaja un mezcla. Imagine que los elementos de dos subarreglos ordenados, 2, 5, 6, 8 y 3, 6, 7, 9, están escritos en tarjetas de papel (para así moverlos con fácilmente). En un tablero coloque en dos columnas las tarjetas para cada subarreglo, una a la izquierda y una a la derecha. En el fondo del tablero, pone ocho posiciones en las que puedan moverse las tarjetas. Entonces, una a una, bajando las tarjetas al fondo de cada columna. En esa etapa compare los números de tarjetas sobre el fondo de las columnas y mueva la tarjeta con el número más pequeño a la próxima posición en el arreglo como un todo. Si en alguna etapa los dos números son iguales, tome, digamos, la tarjeta a la izquierda y muévala a la siguiente posición. Y si una de las columnas queda vacía en alguna etapa, sólo mueva en orden las tarjetas de la otra columna en posición una por una.