Teoría de grafos/Algoritmo/Complejidad de algoritmos

COMPLEJIDAD DE ALGORITMOS

Un programa, por muy correcta que sea su implementación, puede no ser viable(debido al tiempo que necesita para ejecutarse o por la cantidad de espacio que necesita) para algunos tipos de entrada. Cuando realizamos el análisis de un un algoritmo nos refermios al proceso de estimación del tiempo y espacio necesarios para ejecutar el algoritmo. La complejidad de un algoritmo hace referencia a la cantidad de tiempo y espacio necesarios para ejecutar el algoritmo. Con la tecnología actual podemos decir que la memoria de las computadoras es abundante y barata, es por eso que la complejidad del algoritmo se puede limitar al tiempo de ejecución del algoritmo.

---

TIEMPO DE EJECUCIÓN

El tiempo de ejecución de un algoritmo puede diferir dependiendo de la entrada que recibe, es por eso que el tiempo de ejecución de un algortimo se da como una función del tamaño de la entrada. El tiempo de ejecución de un algoritmo se define como T(n), para describirlo mejor se realizara un ejemplo. Ejemplo: <table, border="2">

Num LíneaPotencia(real x, entero positivo n)tiemponúmero 1resultado

$=x$$t_1$

1 2para

$i=1$

hasta

$n-1$

hacer

$t_2$

n-1 3resultado=resultado*x

$t_3$

n-1 4devolver resultado

$t_4$

1

Luego el tiempo de ejecución es:

$T(n)=t_1+(n-1)*t_2+(n-1)*t_3+t_4=(t_2+t_3)*(n-1)+t_1+t_4$

Donde el tiempo de ejecución de este algoritmo tiene orden O(n) osea T(n)=O(n).

pongan mas ejemplos