Notación Asintótica:
Se conocen dos algoritmos para resolver un mismo problema con los siguientes órdenes de complejidad:
f(n) =n (log − 1) y g(n) = (2 log n )^2
Respuestas
Respuesta:
Explicación: Introducción
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.
algoritmo
serie de pasos que nos llevan a resolver efectivamente un problema; podemos decir
que un algoritmo es una idea
programa
un algoritmo escrito usando un lenguaje de programación (por ejemplo, java)
Ante un mismo problema, puede haber mejores ideas y peores ideas acerca de cómo
afrontar su solución. En lo que sigue sólo nos ocuparemos de algoritmos correctos, es
decir, que nos llevan a una solución válida del problema planteado. Dentro de lo que es
correcto, el análisis de algoritmos nos lleva a poder decir si una idea es mejor que otra.
Con un mismo algoritmo podemos escribir un programa mejor o peor. No se puede
escribir un programa correcto basado en un algoritmo incorrecto; pero dentro de la
corrección de la idea, hay programadores y compiladores que son mejores que otros.
1.1 El tamaño
Para cada problema determinaremos una 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 utilizar
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 más 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.
1.2 Recursos
A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios
para que un programa se ejecute. Aunque puede haber muchos parámetros, los mas
usuales son el tiempo de ejecución y la cantidad de memoria (RAM). Ocurre con
frecuencia que ambos parámetros están fijados por otras razones y se plantea la
pregunta inversa: ¿cuál es el tamaño del mayor problema que puedo resolver en T
segundos y/o con M bytes de memoria?
En lo que sigue usaremos esta notación
T(n) – tiempo de ejecución en función del tamaño n del problema
E(n) – espacio (RAM) en función del tamaño n del problema
En lo que sigue nos centraremos casi siempre en tiempo de ejecución, si bien las ideas
desarrolladas son fácilmente aplicables a otro tipo de recursos.
1.3 Tiempo de ejecución
Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en
función de N, lo que denominaremos T(N). Esta función se puede medir físicamente
ADSW complejidad
Página 4 de 31
(ejecutando el programa, reloj en mano), o calcularse sobre el código contando
instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción.
Así, un trozo sencillo de programa como
S1;
for (i= 0; i < N; i++)
S2;
requiere
T(N) = t1 + t2*N
siendo t1 el tiempo que lleve ejecutar la serie "S1" de sentencias, y t2 el que lleve la
serie "S2".
Prácticamente todos los programas reales incluyen alguna sentencia condicional,
haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos
que se le presenten. Esto hace que más que un valor T(N) debamos hablar de un rango
de valores
Tmin(N) ≤ T(N) ≤ Tmax(N)
los extremos son habitualmente conocidos como "caso peor" y "caso mejor". Entre
ambos se hallara algún "caso promedio" o más frecuente.
Cualquier fórmula T(N) incluye referencias al parámetro N y a una serie de constantes
"Ki" que dependen de factores externos al algoritmo como pueden ser la calidad del
código generado por el compilador y la velocidad de ejecución de instrucciones del
ordenador que lo ejecuta. Dado que es fácil cambiar de compilador y que la potencia de
los ordenadores crece a un ritmo vertiginoso1, intentaremos analizar los algoritmos
con algún nivel de independencia de estos factores; es decir, buscaremos estimaciones
generales ampliamente válidas.
1.4 Asíntotas
Por una parte, necesitamos analizar la potencia de los algoritmos independientemente
de la potencia de la máquina que los ejecute e incluso de la habilidad del programador
que los codifique. Por otra, este análisis nos interesa especialmente cuando el
algoritmo se aplica a problemas grandes. Casi siempre los problemas pequeños se
pueden resolver de cualquier forma, apareciendo las limitaciones al atacar problemas
grandes. No debe olvidarse que cualquier técnica de ingeniería, si funciona, acaba