Se hace un kahoot para evaluar temas anteriores

Análisis de algoritmo

Algoritmos

Conjunto finito y precisos de instrucciones de programación para resolver un problema

Es una colección de operaciones computables bien ordenadas efectivas y no ambiguas que cuando son ejecutadas producen un resultado y termina en una cantidad finita de tiempo

• Tiene un input y un output

• Finito: tiene fin

• No ambiguo: que sea preciso

• Efectivo: cumple con el objetivo

• Son deterministicos: los resultados son definidos por el input y los resultados anteriores

Formas de representar un algoritmo

pseudocódigo, prosa, lenguaje de origen, lenguaje formal, diagrama de flujo

• Si se usa el lenguaje de origen, tiende a haber ambigüedad

• Si se usa la notación formal, se ocupa mucho conocimiento

• Si se usa diagramas de flujo, es mas fácil interpretarlo, para todos

Como mejorar un proceso

Cuantificarlo y evaluarlo

Contar la cantidad de veces que ejecutamos procesos fundamentales

Para que analizamos algoritmos

Clasificar problemas

Clasificar algoritmos de acuerdo a su dificultad

Para predecir rendimiento, comparar algoritmos, mejorar los parámetros

Factores que afectan en el tiemp0o de ejecución

• Lenguaje de programación
• Compilador
• Sistema de la computadora(hardware)
• Sistema operativo
• Tamaño del input

Características de interés

• Tiempo
  • Que tanto dura en correr en una pc normal
• Espacio que consume
• Ancho de banda
• Uso de periféricos
  • Que tanto usa
• Cualquier recurso utilizado de la pc

Modelos de analisis

Empírico

• Benchmark

Simulación

• Simulated data
• Casos de prueba

Analítico

• Modelo matemático

Cual usar

• Depende de hasta donde se quiere llegar

Complejidad computacional

• Clasificar problemas computacionales según su dificultad

  • complejidad en tiempo
    • tiempo que toma cada algoritmo
    • representa el algoritmo como una función del tamaño de su input
    • se enfoca en operaciones dominantes
    • se estima contando las instrucciones elementales
    • analiza el rango de crecimiento de una funcion
  • complejidad en espacio

• Clock speed

  • Frecuencia a la que CPU corre
  • measured in hearts or megaheatz

Instrucciones elementales

Instrucciones que siempre toman el mismo tiempo, independientemente del tamaño de input

T es una variable que depende de la arquitectura y el hardware, T es cuanto tiempo requiere para ejecutar las instrucciones elementales

Clasificacion

• Operaciones aritmeticas
• operadores de corrimiento <<,>>
• Operaciones logicas
• Jumps, llamar, retornar
• Declaraciones, asignaciones, acceso a structs indexadas

Declaración mas asignación = 2T comparacion mas entrar a un array = 2T El break es un jump

En un if-else, tiempo de la comparacion if, + el tiempo mayor de los statements internos entre el if y el else

En un for = 2T + N(Statements + t)+(n+1)T, meintras no se use >= o <=

Anlisis de escenarios:

• Mejor
• Average
• Peor

BigO: se concentra donde esta la mayor tasa de crecimiento