Complejidad en los algoritmos

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