orden de complejidad

Vista previa del material en texto

REPÚBLICA BOLIVARIANA DE VENEZUELA 
UNIVERSIDAD JOSÉ ANTONIO PAEZ 
ESCUELA DE INGENIERÍA EN COMPUTACIÓN 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Sección: 305C1 
Romina Betancourt CI: 16052570 
 
Catedra: Algoritmo y Estructuras II 
Prof. Ing. Adolfo Simeone 
 
 
 
San Diego, Diciembre, 2014 
Informe: Orden de Complejidad 
2 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
INDICE 
 
Pág. 
 
1) Definición de orden de complejidad…………………………………………03 
2) La Eficiencia de los Algoritmos……………………………………………..03 
3) Tipos de órdenes de complejidad que existen 
a. Polinómicos (P)………………………………………………………05 
b. No polinómicos (NP)………………………………………………...05 
4) Cuadro comparativo entre al menos 03 algoritmos de ordenamientos, con lo 
siguiente: Orden de complejidad, Cantidad de comparaciones, Cantidad de 
intercambios………………………………………………………………….07 
5) Lista de algoritmos de ordenamiento………………………………………..11 
 
 
 
 
 
 
 
 
3 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
ORDEN DE COMPLEJIDAD 
Se dice que una función es de orden , , si existe una 
constante positiva tal que para se verifica que . 
La estimación que ofrece la notación es una acotación sobre la tasa de 
crecimiento que, aplicado al número de operaciones que se han de hacer en un 
algoritmo, acota el crecimiento que puede tener el coste de realizar el programa al 
aumentar la complejidad del problema. 
Definición: la complejidad del algoritmo es del orden de g(n) (lo 
representaremos por O(g(n)) ) si existe un n0 tal que, para todo valor de n≥n0 , existe 
una constante C tal que |f(n)|≤C |g(n)|. 
 
Con esta definición, si f(n) es un polinomio de grado k, el algoritmo 
correspondiente tendrá una complejidad O(nk), independientemente de cuales sean 
los coeficientes y términos de menor grado del polinomio. De esta forma se formaliza 
la idea de que dos algoritmos de distinta eficiencia tengan la misma complejidad. 
 
Tabla N° 01: En éste caso, la complejidad de los algoritmos es de O(n) y O(2n) 
respectivamente. 
LA EFICIENCIA DE LOS ALGORITMOS. Coste Computacional. 
Uno de los aspectos fundamentales que diferencian a un programador medio 
de un ingeniero en computación es que posee conocimientos de base mucho más 
amplios y elevados es el aspecto de la eficiencia de los algoritmos. 
La idea de la eficiencia de los algoritmos se basa en la premisa de que el 
éxito de un algoritmo no debe de depender en ningún caso de la velocidad ni del 
potencial del sistema en que se ejecute. Un algoritmo eficiente siempre tiene que 
ser mejor que otro que no lo es, aun en el caso de que el segundo se ejecute en un 
sistema claramente superior. Un análisis de coste puede efectuarse en cualquiera 
de los ámbitos de su uso. Los dos más frecuentes son: 
4 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
• El análisis de coste computacional, que mide la eficiciencia de coste temporal 
de los algoritmos y, 
• El análisis de consumo de memoria, que mide la cantidad de memoria 
consumida por un algoritmo. 
Para comparar y analizar la eficiencia de los algoritmos, éstos se consideran escritos en 
un lenguaje de programación de alto nivel, pero aun empleando la misma representación, 
establecer una medida precisa de la eficiencia de un algoritmo no es fácil. En efecto, una 
definición de eficiencia podría ser el número de instrucciones que tiene el programa; sin 
embargo esto no se correspondería, con el concepto intuitivo que tiene eficiencia (según el 
cual, el algoritmo más eficiente sería aquel que tardase menos tiempo en resolver el problema 
sobre una misma máquina), dado que todas las instrucciones no utilizan el mismo tiempo de 
procesador aun realizando la misma función. 
 
 
Tabla N° 02: El primer algoritmo es más costoso que el segundo, a pesar de hacer la 
misma función, a causa de que la potencia es mucho más lenta que el producto. 
 
Es más, el número de instrucciones puede reducirse sin que por ello disminuya 
el número de instrucciones que realmente deben procesarse; así por ejemplo, un bucle 
lo podemos programar tanto con una estructura desde-hasta como con una estructura 
mientras y aunque en este último caso se necesitan más instrucciones 
 
Tabla N° 03: Los dos bucles implican los mismos cálculos, con independencia del 
número de instrucciones de sus estructuras. 
Por otra parte, el propio concepto de tipo de dato se utiliza, entre otras cosas, 
para emplear los métodos más adecuados para realizar las operaciones entre los datos. 
Así, para un mismo procesador, efectuar el producto de dos números es mucho más 
lento si estos números son de tipo Real que si son de tipo Entero, aun siendo los 
mismos números; sin embargo ambos casos son similares desde el punto de vista 
algorítmico. 
5 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
2) Tipos de Ordenes de Complejidad 
a) Polinomial (Clase P): Es cuando un algoritmo tiene una complejidad de 
O(nk). También conocidos como Algoritmos de tiempo polinomial (en el caso de k=1 
se le llama lineal, para k=2 Cuadrático y para k=3 cúbico). 
Los algoritmos de complejidad polinómica se dice que son tratables en el 
sentido de que suelen ser abordables en la práctica. Los problemas para los que se 
conocen algoritmos con esta complejidad se dice que forman la clase P. 
Si por ejemplo, se encuentra que un algoritmo crece con con la tasa 
es correcto decir que es , pero es mucho más preciso afirmar que es
. 
En el caso de la búsqueda secuencial, el algoritmo es , es decir, lineal. 
b) No-Polinomiales (Clase NP): También encontramos algoritmos cuyo coste 
computacional aumenta muy rápidamente con el tamaño del problema, como aquellos 
no polinómicos (por ejemplo ). 
Los problemas cuya complejidad crece exponencialmente son intratables, pues 
solo podrán resolverse en casos muy sencillos. Algunos ejemplos son la búsqueda de 
la distancia más corta entre puntos o la factorización de un número en sus 
componentes primos. Esa complejidad se utiliza en algunos casos, como la 
factorización del número, para construir claves criptográficas. 
Con frecuencia algoritmos que crecen sólo de un modo logarítmico con el 
tamaño de problema ( ), o algo más rápido que linealmente ( ). 
En esos casos consideraremos que son algoritmos eficientes. 
Las funciones de complejidad algorítmica más habituales en las cuales el único 
factor del que dependen es el tamaño de la muestra de entrada n, ordenadas de mayor a 
menor eficiencia son: 
6 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
 
TIPOS Orden Nombre Comentario 
POLINOMIAL O(1) Orden 
constante 
Cuando las instrucciones se ejecutan una vez. 
O(n) Orden lineal Es una complejidad buena y también muy usual. Aparece en la evaluación 
de bucles simples siempre que la complejidad de las instrucciones 
interiores sea constante. 
O(n2) Orden 
cuadrático 
Aparece en bucles o ciclos doblemente anidados. Si n se duplica, el tiempo 
de ejecución aumenta cuatro veces. 
O(n3) Orden cúbico Suele darse en bucles con triple anidación. Si n se duplica, el tiempo de 
ejecución se multiplica por ocho. Para un valor grande de n empieza a 
crecer dramáticamente. 
O(na) Orden 
polinómico 
(a > 3). Si a crece, la complejidad del programa es bastante mala. 
NO 
POLINOMIAL 
O(log n) Orden 
logarítmico 
Complejidad logarítmica. Esta suele aparecer en determinados algoritmos 
con iteración o recursión no estructural, ejemplo la búsqueda binaria. 
O(n log n) Orden cuasi-
lineal 
Se encuentra en algoritmos de tipo divide y vencerás como por ejemplo en 
el método de ordenación quicksort y se considera una buena complejidad. 
Si n se duplica, el tiempo de ejecución es ligeramente mayor del doble. 
O(2n) Orden 
exponencial 
No suelen ser muy útiles en la práctica por el elevadísimo tiempo de 
ejecución. Se dan en subprogramas recursivos que contengan dos o más 
llamadas internas. N 
O(n!) Orden factorial Es el típicode aquellos algoritmos que para un problema complejo prueban 
todas las combinaciones posibles. 
O(n
n
) combinatorio Tan intratable como el anterior. A menudo no se hace distinción entre 
ellos. 
Tabla N° 04: Funciones de complejidad algorítmica. 
7 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
 
3) Dar un ejemplo en pseudocódigo de cada orden de complejidad. 
Orden Nombre Pseudocódigo (inglés o español, ambos incluso) 
O(1) Orden 
constante 
int y, z, k = 10; O(1) 
for(int i = 0; i < k; i++) k * O(1) 
 { y = y + i; O(1) 
 z = z + k; O(1) 
 } 
O(n) Orden lineal 
 
O(na) Orden 
polinómico 
inicio 
 P←a(n) 
 Desde j=n-1 hasta 0 hacer 
 P←P*x+a(i) 
 fin-desde 
fin 
8 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
O(n
2
) Orden 
cuadrático 
 
O(log n) Orden 
logarítmico 
int c, x; O(1) 
for(int i= 0; i < n; i++) O(n) 
{ c = i; O(1) 
 while(c > 0) O(log n) 
 { x = x % c; O(1) 
 c = c / 2; O(1)} 
x = x + 2; O(1) 
} 
O(n log n) Orden cuasi-
lineal 
inicio 
 variables A: arreglo[1..n] entero 
 variables i,j,central:entero 
 variables primero, ultimo: entero 
 para i = 1 hasta n 
 leer(A[i]) 
 Fin para 
 primero = 1 
9 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
 ultimo = n 
 qsort(A[],100) 
Fin 
 
Funcion qsort(primero, ultimo:entero) 
 i = primero 
 j = ultimo 
 central = A[(primero,ultimo) div 2] 
 repetir 
 mientras A[i]central 
 j = j - 1 
 fin mientras 
 si i < = j 
 aux = A[i] 
 A[j] = A[i] 
 A[i] = aux 
 i = i + 1 
 j = j - 1 
 fin si 
 hasta que i > j 
 si primero < j 
 partir(primero,j) 
 fin si 
 si i < ultimo 
 partir(i, ultimo) 
 fin si 
 fin funcion qsort 
 
 
10 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
O(n!) Orden factorial Una versión iterativa: 
PROCEDURE Factorial(n : CARDINAL) : CARDINAL 
BEGIN 
 VAR Resultado,i : CARDINAL ; 
 Resultado :=1 ; 
 FOR i :=1 TO n DO 
 Resultado :=Resultado*i ; 
 END ; 
 RETURN Resultado 
END Factorial 
Una versión recursiva del mismo algoritmo, es: 
PROCEDURE Factorial(n: CARDINAL): CARDINAL; 
BEGIN 
 IF n=0 THEN 
 RETURN 1 
ELSE 
 RETURN ( n* Factorial(n-1) ) 
END 
END Factorial; 
O(n
n
) combinatorio P(0)←0 
C←N 
K←1 
Mientras k<>N hacer 
 C←C/2 
 Desde j=k hasta2*k-1hacer 
 P(j) ←P(j-k)+C 
 fin-desde 
k←k*2 
fin-mientras 
Tabla N° 05: pseudocódigo para cada Orden de Complejidad Importante
11 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
 
1) Realizar un cuadro comparativo entre al menos 03 algoritmos de ordenamiento. 
 
Ordenamiento Orden de 
complejidad Cantidad de comparaciones 
Cantidad de intercambios 
Rápido 
(Quicksort) 
 
O(n*log(n)) 
 
primero = 1 
ultimo = n 
 
Bucle Mientras: 
 j = j - 1 
Condicional i < = j 
 aux = A[i] 
 A[j] = A[i] 
 A[i] = aux 
 i = i + 1 
 j = j - 1 
fin si 
por Inserción O(n2) 
 
Bucle Desde : 
2 + 2 + 2 ... + 2 + 2 =2(n-1) 
Bucle Mientras: 
1 + 2 + 3 + ... + n-2 + n-1 = n(n-1)/2 
Por 
Intercambio 
O(n2) (1 + 2 + + n-1) = (n -1) * (n/2) AUX←A(I) 
A(I)←A(I+1) 
A(I+1)←AUX 
Tabla N° 06: Cuadro Comparativo para tres algoritmos de ordenamiento, en donde se visualiza la cantidad de comparaciones 
y de intercambios dentro a modo pseudocódigo en español.
12 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
 
Lista de algoritmos de ordenamiento: 
 
Algunos algoritmos de ordenamiento agrupados según estabilidad tomando en cuenta 
la complejidad computacional. 
Estables 
Nombre traducido 
Nombre 
original 
Complejidad Método 
Ordenamiento de burbuja Bubblesort O(n²) Intercambio 
Ordenamiento de burbuja 
bidireccional 
Cocktail sort O(n²) Intercambio 
Ordenamiento por selección Selection Sort O(n²) Intercambio 
Ordenamiento por inserción Insertion sort O(n²) Inserción 
Ordenamiento por casilleros Bucket sort O(n) 
No 
comparativo 
Ordenamiento por cuentas Counting sort O(n+k) 
No 
comparativo 
Ordenamiento por mezcla Merge sort O(n log n) Mezcla 
Ordenamiento con árbol 
binario 
Binary tree sort O(n log n) Inserción 
Pigeonhole sort O(n+k) 
 
Ordenamiento Radix 
Radix sort O(nk) 
No 
comparativo 
Distribution 
sort 
O(n³) versión recursiva 
 
Gnome sort O(n²) 
 
13 
Informe de Algoritmo y Estructuras II: Orden de Complejidad 
Inestables 
Nombre traducido 
Nombre 
original 
Complejidad Método 
Ordenamiento Shell Shell sort O(n1.25) Inserción 
 
Comb sort O(n log n) Intercambio 
Ordenamiento por selección Selection sort O(n²) Selección 
Ordenamiento por montículos Heapsort O(n log n) Selección 
 
Smoothsort O(n log n) Selección 
Ordenamiento rápido Quicksort 
Promedio: O(n log n), 
peor caso: O(n²) 
Partición 
 
Several Unique 
Sort 
Promedio: O(n u), 
peor caso: O(n²); 
u=n; u = número único de 
registros 
 
Cuestionables, imprácticos 
Nombre traducido 
Nombre 
original 
Complejidad Método 
 
Bogosort 
O(n × n!), peor: no 
termina 
 
Pancake sorting 
O(n), excepto en 
máquinas de Von 
Neumann 
 
Randomsort 
Promedio: O(n!) Peor: No 
termina 
Tabla N° 07: Algoritmos de Ordenamiento según su estabilidad a modo de consulta.