Semana 1-2

solucion NO general=solucion alambrada, particular

Problemas e instancias:

problema= multiplicar dos numeros cualesquiera. Conjunto infinito (o MUY grande) de instancias, podemos dar los numeros que sea, que nos da solución.

instancia= multiplicar 34x98, donde los numeros ya estan fijados, ya elejidos.

no es instancia= -12x83.7, porque el divide and conquer no usa negativos, ni float.

Podemos decir que un algoritmo no es general, si se encuentra un CONTRAEJEMPLO.

Eficiencia: qué tan rápido se ejecuta un algoritmo para una instancia tamaño n

Empíricamente: a posteriori. Elegir un algoritmo que se programa todo y se hace benchmark, se aplican las mismas instancias y se hace una comparación y se dice cual es  mejor.

Teóricamente: a priori. Se determina matemáticamente la cantidad de recursos(tiempo y espacio) necesarios para cada algoritmo, en función de el tamaño de la instancia. En este enfoque, no se depende del hardware, ni del lenguaje. 

Principio de invariancia:

Se habla del mismo algoritmo, pero diferentes implementaciones, pero puede variar el lenguaje, el hardware(RAM,CPU), la red. Pero el algoritmo tiene el mismo t(n) para a1 y a2.

d y c: Uno acota al otro,  

d=1/c

Entre dos algoritmos, no se difere el tiempo de implementacion, en mas de una constante multiplicativa.

Orden de c*t(n)=  n, n^2, n^3, n^k, c^n

No ocupo unidad de medida para la eficiencia teórica de un programa. 

Caso promedio y peor caso:

Tiempo depende del tamaño de la instancia en particular.