Ed-kjarlos

COMPLEJIDAD ALGORÍTMICA

•
• Un algoritmo será mas eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memorianecesarios para ejecutarlo.
•
• La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:
1.
2. Complejidad Temporal o Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa.3. Complejidad Espacial: Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para elcaso de lamemoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.
•
• Este análisis se basa en las Complejidades Temporales , con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa, intentaremos hallar respuestas en función de dicha N.
•
• El concepto exacto quecuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lógica y complejidad.
•

Tiempo de Ejecución

•
• El tiempo de Ejecuciónde un programa se mide en función de N, lo que designaremos como T(N).
•
• Esta función se puede calcular físicamente ejecutando el programa acompañados de un reloj, o calcularse directamente sobre el código, contando las instrucciones a ser ejecutadas y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de código como:

S1;

for(x = 0; x < N; x++)

S2;Demanda: T(N) = t1 + t2 * N

Donde t1 es el tiempo que lleva ejecutar la serie S1 de sentencias, y t2 es el que lleva la serie S2.

•
• Habitualmente todos los algoritmos contienen alguna sentencia condicional o selectiva, haciendo que las sentencias ejecutadas dependan de la condición lógica, esto hace que aparezca más de un valor para T(N), es por ello que debemos hablar de un rangode valores:

Tmin(N) ≤ T(N) ≤ Tmax(N)

•
• Estos extremos son llamados "el peor caso" y "el mejor caso" y entre ambos se puede hallar "el caso promedio" o el más frecuente, siendo este el más difícil de estudiar; nos centraremos en el " el peor caso" por ser de fácil cálculo y se acerca a "el caso promedio", brindándonos una medida pesimista pero fiable.
•
• Toda función T(N) encierra referencias alparámetro N, y a una serie de constantes Ti dependientes de factores externos al algoritmo. Se tratará de analizar los algoritmos dándoles autonomía frente a estos factores externos, buscando estimaciones generales ampliamente válidas, a pesar de ser demostraciones teóricas.
La notación O grande

Uso

• La notación grande de O tiene dos áreas principales del uso: en matemáticas, seutiliza generalmente para caracterizar el término residual del truncado serie infinita, especialmente serie asintótica; en informática, es útil en análisis de complejidad dealgoritmos.

• La notación primero fue introducida por el teórico del número Paul Bachmann en 1894, en el segundo volumen de su libroAnalytische Zahlentheorie (“analítico teoría del número“), el primer volumen de las cuales(no todavía conteniendo la notación grande de O) fue publicado en 1892. La notación fue popularizada en el trabajo de otro teórico alemán del número Landau de Edmund, por lo tanto a veces se llama un símbolo del Landau. El grande-o, situación para la “orden de”, era originalmente un capital omicron; hoy la mayúscula latina idéntico-que mira O también se utiliza, pero nunca el dígito cero....