programacion c ejercicios resueltos-86

Vista previa del material en texto

228 | Capítulo 6: Ciclos
Análisis de algoritmos
y el trabajo y el tiempo son proporcionales a N 3, siempre que N sea razonablemente grande. Tal fórmula se 
llama cúbica.
En la tabla siguiente se muestra el número de pasos requeridos para cada incremento del exponente 
de N, donde N es un factor de tamaño para el problema, como el número de valores de entrada.
N N0
(Constante)
N1
(Lineal)
N2
(Cuadrática)
N3
(Cúbica)
1 1 1 1 1
10 1 10 100 1 000
100 1 100 10 000 1 000 000
1 000 1 1 000 1 000 000 1 000 000 000
10 000 1 10 000 100 000 000 1 000 000 000 000
100 000 1 100 000 10 000 000 000 1 000 000 000 000 000
Como puede ver, cada vez que el exponente se incrementa en 1, el número de pasos se multiplica por 
orden de magnitud adicional (factor de 10). Es decir, si N se hace 10 veces mayor, el trabajo requerido en un 
algoritmo N 2 se incrementa por un factor de 100, y el trabajo requerido en un algoritmo N 3 crece por un 
factor de 1 000. Para poner esto en términos más concretos, un algoritmo con un ciclo doblemente anidado 
en el que cada ciclo depende del número de valores de datos toma 1 000 pasos para 10 valores de entrada 
y 1 000 billones de pasos para 100 000 valores. En una computadora que ejecuta 1 000 millones de instruc-
ciones por segundo, la ejecución del último caso tomaría cerca de 12 días.
En la tabla se muestra también que los pasos fuera del ciclo interno representan una porción signifi -
cativa del número total de pasos cuando N crece. Debido a que el ciclo interno domina el tiempo total, se 
clasifi ca la complejidad de un algoritmo de acuerdo con el orden más alto de N que aparece en su expre-
sión de complejidad, llamado orden de magnitud, o simplemente orden, de esa expresión. Así, se habla de 
algoritmos que tienen “complejidad de orden N cuadrada” (o cúbica, etcétera) o se describen con los que se 
denomina notación O mayúscula. La complejidad se expresa al escribir entre paréntesis el término de orden 
máximo con una O mayúscula enfrente. Por ejemplo, O(1) es tiempo constante, O(N) es tiempo lineal, O(N2) 
es tiempo cuadrático y O(N3) es tiempo cúbico.
Determinar las complejidades de distintos algoritmos permite comparar el trabajo que requieren 
sin tener que programarlos y ejecutarlos. Por ejemplo, si usted tuviera un algoritmo O(N2) y un algoritmo 
lineal que realiza la misma tarea, tal vez elegiría el algoritmo lineal. Se dice probablemente porque un al-
goritmo O(N2) podría ejecutar en realidad menos pasos que un algoritmo O(N) para valores pequeños de 
N. Recuerde que si el factor de tamaño N es pequeño, las constantes y los términos de orden menor en la 
expresión de complejidad pueden ser signifi cativos.
Considérese un ejemplo. Suponga que el algoritmo A es O(N2) y que el algoritmo B es O(N). Para valo-
res grandes de N, normalmente se elegiría el algoritmo B porque requiere menos trabajo que A. Pero su-
ponga que en el algoritmo B, S0 = 1 000 y S1 = 1 000. Si N = 1, entonces la ejecución del algoritmo B requiere 
2 000 pasos. Ahora suponga que para el algoritmo A, S0 = 10, S1 = 10 y S2 = 10. Si N = 1, entonces el algorit-
mo A requiere sólo 30 pasos. A continuación se muestra una tabla en la que se compara el número de pasos 
que requieren estos dos algoritmos para distintos valores de N.
▼(continúa)
DALE06.indd 228DALE06.indd 228 4/12/06 19:03:494/12/06 19:03:49
 www.FreeLibros.me
Análisis de algoritmos
N Algoritmo A Algoritno B
1 30 2 000
2 70 3 000
3 130 4 000
10 1 110 11 000
20 4 210 21 000
30 9 310 31 000
50 25 510 51 000
100 101 010 101 000
1 000 10 010 010 1 001 000
10 000 1 000 100 010 10 001 000
De esta tabla se puede ver que el algoritmo A en O(N2) es en realidad más rápido que el algoritmo B de 
O(N), hasta el punto en que N es igual a 100. Más allá de ese punto, el algoritmo B se hace más efi ciente. Así, 
si se sabe que N es siempre menor que 100 en un problema particular, se elegiría el algoritmo A. Por ejem-
plo, si el factor de tamaño N es el número de puntuaciones de prueba en un examen y el tamaño de clase 
está limitado a 30 alumnos, el algoritmo A sería más efi ciente. Por otro lado, si N es el número de puntacio-
nes en una universidad con 25 000 alumnos, se elegiría el algoritmo B.
Las expresiones constante, lineal, cuadrática y cúbica son ejemplos de expresiones polinomiales. Por 
consiguiente, se dice que los algoritmos cuya complejidad se caracteriza por esta clase de expresiones se 
ejecutan en tiempo polinomial y forman una amplia clase de algoritmos que abarcan todo lo que se ha ex-
plicado hasta aquí.
Además de los algoritmos de tiempo polinomial, en el capítulo 13 se encuentra un algoritmo de tiem-
po logarítmico. Hay también algoritmos de clase factorial (O(N!)), exponencial (O(NN)) e hiperexponencial 
(O(NN
N
)), cuya ejecución puede requerir vastas cantidades de tiempo y están fuera del alcance de este libro. 
Por ahora, el punto importante a recordar es que diferentes algoritmos que resuelven el mismo problema 
pueden variar de modo importante en la cantidad de trabajo que realizan.
Caso práctico de resolución de problemas
Diseño de estudio de grabación
PROBLEMA Usted ha entrado a trabajar a una empresa consultora que se especializa en convertir habitaciones 
en estudios de grabación. La empresa le ha pedido que escriba un programa que introduzca un conjunto de me-
diciones de sonoridad para una habitación y que imprima estadísticas básicas. Las mediciones se hacen al tocar 
una serie de 12 tonos distintos y registrar las lecturas de un medidor de nivel de sonido en un archivo. Las lecturas 
del medidor varían de 50 a 126 decibeles (una medida de sonoridad). Sin embargo, su programa producirá las 
mediciones en relación con el primer tono; es decir, mostrará cuánto difi ere cada lectura de la primera. Una vez 
que se han leído todos los datos, el programa imprimirá las lecturas máxima y mínima.
ENTRADA Doce números reales, que representan las lecturas del medidor, en el archivo “acoustic.dat”.
Caso práctico de resolución de problemas | 229
DALE06.indd 229DALE06.indd 229 4/12/06 19:03:584/12/06 19:03:58
 www.FreeLibros.me
230 | Capítulo 6: Ciclos
SALIDA Los 12 valores de entrada (impresos por eco) y sus valores respecto a la primera lectura. Al fi nal del 
programa, el valor real, valor relativo y número de secuencia de la lectura máxima y la mínima.
ANÁLISIS Esto es fácil de hacer a mano. Simplemente se explora la lista, restando el primer valor de cada valor 
de la lista. Conforme se explora la lista, se sigue la pista de cuál valor es el máximo y cuál es el mínimo.
¿Cómo se traduce este proceso en un algoritmo? Considérese con más detenimiento lo que se está hacien-
do. Para hallar el número más grande en una lista, se comparan los números primero y segundo y se recuerda el 
más grande. Luego, se compara ese número con el tercero, recordando el más grande. El proceso se repite para 
todos los números, y el que se recuerda al fi nal es el mayor. Se emplea el mismo proceso para hallar el número 
menor, sólo que se recuerda el número más pequeño en lugar del más grande. Considere un conjunto de datos 
de muestra:
Número de lectura Lectura real Lectura relativa
1 86.0 0.0
2 86.5 0.5
3 88.0 2.0
4 83.5 –2.5
5 88.3 2.3
6 89.6 3.6
7 80.1 –5.9
8 84.0 –2.0
9 86.7 0.7
10 79.3 –6.7
11 74.0 –12.0
12 73.5 –12.5
La lectura máxima fue la número 6 en 89.6 decibeles. La mínima fue la lectura 12 en 73.5 decibeles.
“Explorar la lista” en el algoritmo a mano se traduce en un ciclo. Ahora que se entiende el proceso, se diseñará 
el algoritmo de iteración con la lista de comprobación.
1. ¿Cuál es la condición en que termina el ciclo? Debido a que hay exactamente 12 valores en un con-
junto de lecturas, se usa un contador para controlar el ciclo. Cuando pasa de 12, termina el ciclo.
2. ¿Cómo se debe inicializar la condición? El primer valor será introducido antes del ciclo, debido a que 
es un caso especial; es el valor que se resta de los otros para obtener sus valoresrelativos. También, 
su valor relativo es automáticamente 0.0. Así, la primera iteración del ciclo obtiene el segundo 
valor, de modo que el contador comenzará en 2.
3. ¿Cómo se debe actualizar la condición? El contador se debe incrementar al fi nal de cada iteración.
4. ¿Cuál es el proceso que se repite? El proceso lee un valor, lo imprime por eco, resta el primer valor 
del nuevo, imprime el resultado y comprueba si el nuevo valor debe remplazar al valor alto o bajo 
actual.
5. ¿Cómo se debe inicializar el proceso? Se debe leer el primer número. Su valor relativo se imprime au-
tomáticamente como 0.0. Es el valor inicial alto y bajo, y también se guarda como la lectura base. El 
número de secuencia para los valores alto y bajo se establecerá en 1 y sus valores relativos serán 0.0.
6. ¿Cómo se debe actualizar el proceso? En cada iteración, se introduce una nueva lectura actual. Si 
la lectura actual es mayor que el valor alto (high), ésta remplaza al valor alto actual. Si la lectura 
actual es menor que el valor bajo (low) actual, entonces se convierte en el nuevo valor bajo. Se debe 
guardar también el número de lectura de los valores máximo y mínimo y sus valores relativos.
DALE06.indd 230DALE06.indd 230 4/12/06 19:04:054/12/06 19:04:05
 www.FreeLibros.me