Algoritmo

Algoritmos

Un algoritmos es un conjunto de reglas definidas, claras, ordenadas y finitas que sirven para resolver un problema determinado. En un algoritmo ya se debe de conocer que clase de respuesta va a dar. Los resultados que devuelve el algoritmo están definidos con las entradas y salidas de los pasos.

Análisis de algoritmos

Se usa para estimar cuantos recursos va a requerir un algoritmo. Es útil para evaluar si un algoritmo es útil o no para su uso dentro de una aplicación. Para esto se comparan dos algoritmos dentro de la misma aplicación para determinar cual es mas eficiente. Se califican los problemas y algoritmos por dificultad. El análisis también es útil para predecir el desempeño del algoritmo. Al final se comprenderá mejor como implementar el algoritmo para poder mejorarlo si es necesario.

El tiempo de ejecución de un algoritmo se puede ver afectado por:

• Hardware
• Compilador
• Lenguaje de programación
• Sistema Operativo
• Desarrollador
• Tamaño de entrada
• Aplicaciones corriendo computadora

Para comparar dos algoritmos se toman en cuenta el tiempo que toman en terminar su función y el espacio que ocupan en el disco. Otras factores a tomar en cuenta es la banda de ancha, velocidad del disco.

Tipos de medidas:

Empírica

• Benchmark

Simulación

• Datos simulados
• Casos de prueba

Analítico

• Modelo matemático(tiempo y espacio)

Complejidad computacional

• Clasifica problemas computacionales acorde a su dificultad
• Representa ele algoritmo e función al tamaño de la entrada

Time complexity

• Clasifica la cantidad de tiempo que le toma al algoritmo terminar el proceso.

El tiempo se toma como el tiempo real, el tiempo del CPU

Space complexity

Representa al algoritmo en función al tamaño de la entrada.

Big-O: Es una notación que expresa

Tiempo constante

Las siguientes operaciones toman tiempo constante:

• Asignar una valor a una variable
• Insertar un elemento en un array
• Determinar si un numero binario es par o impar
• Obtener un elemento i de un array
• Obtener un valor de una tabla hash (Diccionario) con una llave

Tiempo logarítmico

El tiempo logarítmico se hace más lento a medida que n crece.

Ejemplos

• Búsqueda binaria
• Insertar o borrar un elemento de un heap

Tiempo lineal

El loop se ejecuta N veces Asume que

Linearithmic time

Es capas de un desempeño bastante bueno en conjuntos grandes de datos

Ejemplos:

• Heapsort
• Merge sort
• Quick sort

Quadratic time

Ejemplos:

• Búsqueda lineal en una matriz
• Complejidad de tiempo en un quick sort, el cual es alto
• Insertion sort