Algoritmos Generalidades

Algoritmo: Es un buen definido procedimiento computacional que toma algunos valores, o un conjunto de valores, como entrada y produce algunos valores, o conjunto de valores, como salida. Así es como un algoritmo es una secunecia de pasos computacionales que transforma una entrada en una salida.

Analisis de Algoritmo: Analizar un algortimo es predecir los recursos que el algoritmo requiere. Ocacionalmente, recursos tales como memoria, ancho de banda de comunicación, o número de compuertas lóginas son de gran interés, pero más común es la cantidad de tiempo computacional la que se desea medir.

Tamaño de la entrada: Depende del problema en estudio. Puede ser número de datos a ser ordenados, número de bits a ser multiplicados, o el par número de nodos y arcos de un grafo.
Tiempo de ejecución: Es el número de operaciones primitivas o "pasos" ejecutados.
Ejemplo:
    Consideremos el algoritmo "insertion-sort"
 
Algoritmo Costo Veces
InsertionSort(int A[], int n) { c1 1
    int j, i, key; c2 1
    for (j=1;  j<n; j++) { c3 n-1
        key = A[j]; c4 n-1
        i = j-1; c5 n-1
        while( i>=0  && A[i] > key ) { c6 Suma desde j=1 hasta n-1 de tj
            A[i+1] = A[i]; c7 Suma desde j=1 hasta n-1 de (tj - 1)
            i --; c8 Suma desde j=1 hasta n-1 de (tj -1)
        } 0 -
        A[i+1]=key; c9 n-1
    } 0 -
} 0 -

Definiciones