Resumen Notacion O Grande

Estructura de Datos
Notacin O Grande
Raramente existe un nico algoritmo para resolver un problema determinado. Cuando se comparan dos
algoritmos diferentes que resuelven el mismo problema, normalmente se encontrar que un algoritmo
es un orden de magnitud ms eficiente que el otro. La eficiencia de un algoritmo es la propiedad
mediante la cual un algoritmo debe alcanzar la solucin al problema en el tiempo ms corto posible o
utilizando la cantidad ms pequea posible de recursos fsicos y que sea compatible con su exactitud o
correccin Cmo medir la eficiencia de un algoritmo o programa informtico?
Formato general de la eficiencia
En general, el formato se puede expresar mediante una funcin:
f (n) = eficiencia
Es decir, la eficiencia del algoritmo se examina como una funcin del nmero de elementos que tienen
que ser procesados.
Bucle lineal: f(n) = n
Bucle logartmico: f(n) = log n
Bucle logartmico lineal: f(n) = n * log n
Bucle cuadrtico dependiente: f(n) = n(n+1)/2
Bucle cuadrtico dependiente: f(n) = n2
Bucle cbico: f(n) = n3
Anlisis de rendimiento
La medida del rendimiento de un programa se consigue mediante la complejidad del espacio y del
tiempo de un programa.
La complejidad del espacio de un programa es la cantidad de memoria que se necesita para ejecutarlo
hasta la complecin (terminacin). El avance tecnolgico proporciona hoy en da memoria abundante;
por esa razn, el anlisis de algoritmos se centra fundamentalmente en el tiempo de ejecucin.
La complejidad del tiempo de un programa es la cantidad de tiempo de computadora que se necesita
para ejecutarlo. Se utiliza una funcin, T(n), para representar el nmero de unidades de tiempo tomadas
por un programa o algoritmo para cualquier entrada de tamao n. Si la funcin T(n) de un programa es
T(n) = c * n, entonces el tiempo de ejecucin es linealmente proporcional al tamao de la entrada sobre
la que se ejecuta. Tal programa se dice que es de tiempo lineal o, simplemente lineal. El tiempo de
ejecucin de un programa con entrada de tamao n se podr medir desde diferentes puntos de vista:
1. Peor caso. Indica el tiempo peor que se puede tener. Este anlisis es perfectamente adecuado
para algoritmos cuyo tiempo de respuesta es crtico; por ejemplo, para el caso del programa de
control de una central nuclear. Es el que se emplea en este libro.
2. Mejor caso. Indica el tiempo mejor que podemos tener.
3. Caso medio. Se puede computar T(n) como el tiempo medio de ejecucin del programa sobre
todas las posibles ejecuciones de entradas de tamao n
Notacin O-Grande
La alta velocidad de las computadoras actuales hace que la medida exacta de la eficiencia de un
algoritmo no sea una preocupacin vital en el diseo, pero s el orden general de magnitud de la misma.
Por consiguiente, no se necesita determinar la medida completa de la eficiencia, basta con calcular el
factor que determina la magnitud. Este factor se define como O grande, que representa est en el
orden de y se expresa como O(n), es decir, en el orden de n.
La notacin O indica la cota superior del tiempo de ejecucin de un algoritmo o programa. As, en lugar
de decir que un algoritmo emplea un tiempo de 4n-1 en procesar un array de longitud n, se dir que
emplea un tiempo O(n) que se lee O grande de n, o bien O de n y que informalmente significa
algunos tiempos constantes n.
Con la notacin O se expresa una aproximacin de la relacin entre el tamao de un problema y la
cantidad de proceso necesario para hacerlo. Por ejemplo, si
f(n) = n2 2n +3 entonces f(n) es O(n2).
Una funcin f(x) puede estar acotada superiormente por un nmero indefinido de funciones
a partir de ciertos valores x0,
f(x) g(x) h(x) k(x) ...
La complejidad asinttica de la funcin f(x) se considera que es la cota superior mas ajustada:
f(x) = O(g(x))
Determinar la notacin O
La notacin O grande se puede obtener de f(n) utilizando los siguientes pasos:
1. En cada trmino, establecer el coeficiente del trmino en 1.
2. Mantener el trmino mayor de la funcin y descartar los restantes. Los trminos se ordenan de
menor a mayor:
log2n
n
nlog2n
n2
n3 ... nk
2n
n!
Propiedades de la notacin O-grande
De la definicin conceptual de la notacin O se deducen las siguientes propiedades de la notacin O.
1. Siendo c una constante, c*O(f(n)) = O(f(n)).
2. O(f(n)) + O(g(n)) = O(f(n)+g(n)).
3. Maximo(O(f(n)),O(g(n))) = O(Maximo(f(n),g(n)).
4. O(f(n)) * O(g(n)) = O(f(n)*g(n)).
5. O(loga(n)) = O(logb(n)) para a, b > 1.
6. O(log(n!)) = O(n*log(n)).
) = O(nk+1)
7. Para k > 1 O(
8. O(
()
( )).

Resumen Notacion O Grande

Cargado por

Copyright:

Formatos disponibles

Resumen Notacion O Grande

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Resumen Notacion O Grande

Cargado por

Copyright:

Formatos disponibles

Estructura de Datos

f(x) g(x) h(x) k(x) ...

También podría gustarte