Complejidad de 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 la com-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ón está dado por los n datos deentrada

NOTACIÓN ARITMÉTICA
Notación asintótica “O” grande se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función, es decir, su utilidad radica en encontrarun límite superior del tiempo de ejecución de un algoritmo es decir el peor caso.
La definición de esta notación es la siguiente:
Una función g(n) pertenece a O (f(n)) si y solo si existen lasconstantes c y n. tales que:
g(n) | < = | c · f(n) |
para todo n > = n. y se tiene que T(n) < = cn.
Nota: el orden de magnitud de una función es el orden del término de la función más granderespecto de n.
Notación asintótica “Omega” grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de T(n), y significa que existe una constante c tal que T(n) es mayor oigual a c(g(n)) para un número infinito de valores n.

Selección de un algoritmo

Una de las características primordiales en la selección de un algoritmo es que este sea sencillo de entendercalcular codificar y depurar, así mismo que utilice eficientemente los recursos del ordenador y se ejecute con la mayor rapidez posible con un eficaz uso de memoria dinámica y estática.
También paraseleccionar correctamente el mejor algoritmo es necesario realizar estas preguntas:
* ¿Qué grado de orden tendrá la información que vas a manejar?
Si la información va a estar casi ordenada y noquieres complicarte, un algoritmo sencillo como el ordenamiento burbuja será suficiente. Si por el contrario los datos van a estar muy desordenados,
un algoritmo poderoso como Quicksort puede ser...