Complejidad En Algoritmos
Páginas: 8 (1922 palabras)
Publicado: 26 de noviembre de 2012
Unidad de aprendizaje: Criptografía
Fecha: 31/Octubre/2012
Time Complexity
Es la medida de la cantidad de tiempo requerido para ejecutar un algoritmo.
Big O Notation (O => Order of)
Notación usada comúnmente para describir la tasa de crecimiento del tiempo de ejecución o uso de memoria usada por un algoritmo.
Usualmente describe el peor caso del tiempo de ejecución de unalgoritmo.
Complejidad en algoritmos
* Constant Time => O(1)
Se necesita una cantidad de tiempo fija para ejecutar un programa o algoritmo. No dependen del número de inputs o entradas.
Por ejemplo, cuando en un lenguaje se quiere escribir una función que retorne falso o verdadero basado en el valor del primer elemento de un arreglo. El programa necesita de entrada un arreglo conenteros. Si el primer entero del arreglo en mayor que 0, la función regresa verdadero, en cualquier otra condición, la función regresa falso.
En este ejemplo, el tiempo de ejecución de la función no depende del número de elementos. Este solo checa el primer elemento y regresa el resultado. A la función no le importa si el arreglo tiene un entero o un millón de enteros. De esto podemos decir que eltiempo de ejecución de esta función es constante.
* Inverse Ackerman Time
La función de Ackerman es ejemplo clásico de recursividad. Es una función que crece muy rápidamente (tanto es su valor como en su árbol de llamadas), esta definida:
Para valores pequeños de m, como 1, 2 o 3 A crece relativamente lento con respecto a n (a lo sumo exponencialmente). Para m >= 4 crece más rápidoSi hablamos de la función inversa, esta crece muy lentamente. Se denota con α. De hecho, α(n) es menor que 5 para cualquier tamaño de entrada n, que ya para A(4, 4) esta en el orden de .
Aparece en algunos algoritmos como por ejemplo, “disjoint-set data structure” y “Chazelle’s algorithm for minimun spanning trees”.
* Logaritmic Time => Log2N
Las funciones o algoritmos necesitanuna cantidad de tiempo que es logarítmicamente proporcional al numero de elementos de entrada.
Asumir que se quiere buscar un número (el 41) dentro de un conjunto de elementos ordenados. Por ejemplo, tenemos el siguiente conjunto {3, 5, 8, 9, 41}.
Empezamos con el elemento de en medio y hacemos la comparación. El mejor caso se da cuando encontramos el número al primer intento. Pero elelemento de en medio es el 8. Que no es el número que estamos buscando. Debido a que sabemos que el conjunto de elementos esta ordenado, podemos determinar que debemos de buscar el número desde el elemento de en medio hasta el último. Simplemente ignoramos la primera mitad del conjunto. De nuevo aplicamos una lógica similar a la mitad del conjunto. Continuaremos con esto, hasta encontrar el elemento ollegar a la conclusión de que este no existe.
Como se puede ver en cada intento, el número de elementos es reducido a la mitad. Entonces en un conjunto de 1000 números, el peor escenario sería el siguiente:
* Después del primer intento, nos quedan 500 números.
* Después del segundo intento, nos quedan 250 números.
* Después del tercer intento, nos quedan 125 números.
* Despuésdel cuarto intento, nos quedan 62 números.
* Después del quinto intento, nos quedan 31 números.
* Después del sexto intento, nos quedan 15 números.
* Después del séptimo intento, nos quedan 7 números.
* Después del octavo intento, nos quedan 3 números.
* Después del noveno intento, nos queda 1 número.
* Después del decimo intento, ya conocemos el resultado. Ya sea queencontremos el número buscado o determinemos que no se encuentra dentro del conjunto.
Como se puede ver, en el peor escenario necesitamos solamente 10 comparaciones.
En términos matemáticos, si el número de elementos es N, revisaremos log2N números. Por lo tanto es llamada función logarítmica.
Los arboles de búsqueda binarios tienen este tipo de complejidad cuando queremos localizar un...
Fecha: 31/Octubre/2012
Time Complexity
Es la medida de la cantidad de tiempo requerido para ejecutar un algoritmo.
Big O Notation (O => Order of)
Notación usada comúnmente para describir la tasa de crecimiento del tiempo de ejecución o uso de memoria usada por un algoritmo.
Usualmente describe el peor caso del tiempo de ejecución de unalgoritmo.
Complejidad en algoritmos
* Constant Time => O(1)
Se necesita una cantidad de tiempo fija para ejecutar un programa o algoritmo. No dependen del número de inputs o entradas.
Por ejemplo, cuando en un lenguaje se quiere escribir una función que retorne falso o verdadero basado en el valor del primer elemento de un arreglo. El programa necesita de entrada un arreglo conenteros. Si el primer entero del arreglo en mayor que 0, la función regresa verdadero, en cualquier otra condición, la función regresa falso.
En este ejemplo, el tiempo de ejecución de la función no depende del número de elementos. Este solo checa el primer elemento y regresa el resultado. A la función no le importa si el arreglo tiene un entero o un millón de enteros. De esto podemos decir que eltiempo de ejecución de esta función es constante.
* Inverse Ackerman Time
La función de Ackerman es ejemplo clásico de recursividad. Es una función que crece muy rápidamente (tanto es su valor como en su árbol de llamadas), esta definida:
Para valores pequeños de m, como 1, 2 o 3 A crece relativamente lento con respecto a n (a lo sumo exponencialmente). Para m >= 4 crece más rápidoSi hablamos de la función inversa, esta crece muy lentamente. Se denota con α. De hecho, α(n) es menor que 5 para cualquier tamaño de entrada n, que ya para A(4, 4) esta en el orden de .
Aparece en algunos algoritmos como por ejemplo, “disjoint-set data structure” y “Chazelle’s algorithm for minimun spanning trees”.
* Logaritmic Time => Log2N
Las funciones o algoritmos necesitanuna cantidad de tiempo que es logarítmicamente proporcional al numero de elementos de entrada.
Asumir que se quiere buscar un número (el 41) dentro de un conjunto de elementos ordenados. Por ejemplo, tenemos el siguiente conjunto {3, 5, 8, 9, 41}.
Empezamos con el elemento de en medio y hacemos la comparación. El mejor caso se da cuando encontramos el número al primer intento. Pero elelemento de en medio es el 8. Que no es el número que estamos buscando. Debido a que sabemos que el conjunto de elementos esta ordenado, podemos determinar que debemos de buscar el número desde el elemento de en medio hasta el último. Simplemente ignoramos la primera mitad del conjunto. De nuevo aplicamos una lógica similar a la mitad del conjunto. Continuaremos con esto, hasta encontrar el elemento ollegar a la conclusión de que este no existe.
Como se puede ver en cada intento, el número de elementos es reducido a la mitad. Entonces en un conjunto de 1000 números, el peor escenario sería el siguiente:
* Después del primer intento, nos quedan 500 números.
* Después del segundo intento, nos quedan 250 números.
* Después del tercer intento, nos quedan 125 números.
* Despuésdel cuarto intento, nos quedan 62 números.
* Después del quinto intento, nos quedan 31 números.
* Después del sexto intento, nos quedan 15 números.
* Después del séptimo intento, nos quedan 7 números.
* Después del octavo intento, nos quedan 3 números.
* Después del noveno intento, nos queda 1 número.
* Después del decimo intento, ya conocemos el resultado. Ya sea queencontremos el número buscado o determinemos que no se encuentra dentro del conjunto.
Como se puede ver, en el peor escenario necesitamos solamente 10 comparaciones.
En términos matemáticos, si el número de elementos es N, revisaremos log2N números. Por lo tanto es llamada función logarítmica.
Los arboles de búsqueda binarios tienen este tipo de complejidad cuando queremos localizar un...
Leer documento completo
Regístrate para leer el documento completo.