Complejidad en los algoritmos
Cristian Ramiro Melendez Almaraz
La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.
A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parametros, los mas usuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria? En lo que sigue nos centraremos casi siempre en el parametro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.
Para cada problema determinaremos un medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N. El concepto exacto que mide N depende de la naturaleza del problema. Así, para un vector se suele utizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es mas importante considerar el número de arcos, dependiendo del tipo de problema a resolver); en un fichero se suele usar el número de registros, etc. Es imposible dar una regla general, pues cada problema tiene su propia lógica de coste.
Es claro que para cada algoritmo la cantidad de recursos (tiempo,
memoria) utilizados depende fuertemente de los datos de
entrada. En general, la cantidad de recursos crece a medida que
crece el tamaño de la entrada
el análisis de esta cantidad de recursos no es viable de ser
realizado instancia por instancia
se introducen las funciones de cantidad de recursos en base al
tamaño de la entrada. Este tamaño puede ser la cantidad de
dígitos para un número, la cantidad de elementos para un
arreglo, la cantidad de caracteres de una cadena, etc.
en ocasiones es útil definir el tamaño de la entrada en base a
dos o más magnitudes. Por ejemplo, para un grafo es frecuente
utilizar la cantidad de nodos y la de arcos
Pablo R. Fillottrani Algoritmos y Complejidad
Algoritmos y Algoritmia
Problemas e instancias
Tipos de análisis de eficiencia
Algunos ejemplos simples
dado un algoritmo A, el tiempo de ejecución tA(n) de A es la
cantidad de pasos, operaciones o acciones elementales que
debe realizar el algoritmo al ser ejecutado en una instancia de
tamaño n
el espacio eA(n) de A es la cantidad de datos elementales que el
algoritmo necesita al ser ejecutado en una instancia de tamaño
n, sin contar la representación de la entrada ni de la salida
estas definiciones son ambiguas (¿porqué?)
Pablo R. Fillottrani Algoritmos y Complejidad
Algoritmos y Algoritmia
Problemas e instancias
Tipos de análisis de eficiencia
Algunos ejemplos simples
ambigüedades de la definición de tiempo de ejecución:
No está claramente especificado cuáles son las operaciones o los
datos elementales. Este punto quedará determinado en cada
análisis en particular, dependiendo del dominio de aplicación
Dado que puede haber varias instancias de tamaño n, no está
claro cuál de ellas es la que se tiene en cuenta para determinar la
cantidad de recursos necesaria
para resolver este último punto se definen distintos tipos de
análisis de algoritmos
Pa
MULTIPLICACIÓN DE DOS NÚMEROS ENTEROS
Algoritmos:
Clásico
9 8 1
_ 1 2 3 4
3 9 2 4
2 9 4 3
1 9 6 2
9 8 1
1 2 1 0 5 5 4
A la inglesa
9 8 1
_ 1 2 3 4
9 8 1
1 9 6 2
2 9 4 3
3 9 2 4
1 2 1 0 5 5 4
A la rusa
981 1234 1234
490 2468
245 4936 4936
122 9872
61 19744 19744
30 39488
15 78976 78976
7 157952 157952
3 315904 315904
1 631808 631808
1210554
Pablo R. Fillottrani Algoritmos y Complejidad
Algoritmo: Ordenamiento por Inserción
FOR j ::= 2 TO n
x ::= A[j]
i ::= j-1
WHILE i> 0 and A[i]>x
A[i+1] ::= A[i]
i ::= i-1
ENDWHILE
A[i+1] ::= x
ENDFOR
costo veces
c1 n
c2 n1
c3 n1
c4 ån1
j=1 tj
c5 ån1
j=1 (tj 1)
c6 ån1
j=1 (tj 1)
c8 n1
Pablo R. Fillottrani Algoritmos y Complejidad
Algoritmos y Algoritmia
Problemas e instancias
Tipos de análisis de eficiencia
Algunos ejemplos simples
ORDENAR UN ARREGLO
Algoritmo: Ordenamiento por Inserción
Costo de la ejecución del algoritmo:
T(n) = c1n+c2(n1)+c3(n1)+c4
n1
å
j=1
tj +c5
n1
å
j=1
(tj 1)+
+c6
n1
å
j=1
(tj 1)+c8(n1)
= (c1 +c2 +c3 +c8)n(c2 +c3 +c8)+(c4 +c5 +c6)
n1
å
j=1
tj (c5 +c6)
n1
å
j=1
1
demasiado complicado para ser útil. No es posible simplificar
veremos más adelante como tratar estas funciones
Pablo R. Fillottrani Algoritmos y Complejidad
Algoritmos y Algoritmia
Problemas e instancias
Tipos de análisis de eficiencia
Algunos ejemplos simples
NÚMEROS DE FIBONACCI
Fn =
_
i si i = 0 o i = 1
Fn1+Fn2 si i _ 2
Algoritmo: naïve, recursivo
function FIB1(n)
IF n<2
return n
ELSE
return Fib1(n-1)+Fib1(n-2)
Pablo R. Fillottrani Algoritmos y Complejidad
Algoritmos y Algoritmia
Problemas e instancias
Tipos de análisis de eficiencia
Algunos ejemplos simples
NÚMERO DE FIBONACCI
Algoritmo: naïve, recursivo
definiendo el tiempo de ejecución del algoritmo anterior, se
obtiene la siguiente recurrencia
TFIB1(n) =
_
a si n < 2
TFIB1(n1)+TFIB1(n2)+b si n _ 2
asi como está, esta función tampoco es útil para analizar y
comparar el algoritmo
