Algoritmos

COMPLEJIDAD DE LOS ALGORITMOS

La complejidad de los algoritmos nos representa o dice el tiempo de ejecución
de cialquier programa en base a los 'n' datos de entrada. Por lo tanto lacom-
plejidad de cualquier algorito se expresa en los siguientes términos:

T(n) Funcion de la complejidad

la cual se interpreta de la siguiente manera:

El tiempo de ejecuciónestá dado por los n datos de entrada

REGLAS PARA EL CALCULO DE LA COMPLEJIDAD

DE UN ALGORITMO

1. El tiempo de ejecución de cada sentencia simple puede tomarse comocomplejidad de T(1)
2. Para las sentencias de bifurcación (if, case) el resultante de la complejidad será T(1)
3. La complejidad para los bucles (for, repeat, while) independientes seráT(n)
4. La complejidad para los bucles anidados será: T(nm) donde m nos representa el numero de bucles anidados

Ejemplo 1:
El algoritmo a1 tarda n segundos en resolver un problemapara una determinada cantidad
de datos mientras que el algoritmo n2 + 400n tarda también un determinado
tiempo en resolver el mismo problema.
Determine cual de los dos algoritmos esmás eficiente en base a los datos de entrada
|a1 | |a2 |
|5n2 |>= |n2+400n |
|4n2 |>= |400n |
|n2 |>= |100n |
|n |>= |100 |
|n |< |100 |a1 esmejor |
|n |>= |100 |a2 es mejor |

Ejemplo 2:
Dado el siguiente algoritmo determine su complejidad
|INICIO | | |T(1) |
||Leer a,b,c,sum | |T(1) |
| |if a>3 then b=c*a | |T(1) |
| |desde a=1 hasta b | |T(n) |
| ||sum=sum+a |T(1) |
| |Fin | |T(1) |
|FINAL | | |T(1) |

La complejidad del algoritmo es T(n)