Análisis de Complejidad de Algoritmos: Teoría y Ejemplos

Análisis de Complejidad de Algoritmos

Un algoritmo es un conjunto de pasos que nos permiten resolver un problema en concreto.

Necesitamos recursos para poder efectuar el algoritmo, ya sea de tiempo de ejecución o de espacio. Así, un buen algoritmo es un conjunto de pasos que nos permiten resolver un problema en concreto de forma eficiente. Para calcular el tiempo que tardamos en ejecutar un algoritmo podemos hacerlo mediante tres tipos:

• Análisis de caso medio.
• Análisis de caso peor.
• Análisis de caso mejor.

Vamos a analizar el tiempo para una suficientemente grande utilizando la notación "O" (leído "o grande"). Así: (leído " es de orden cúbico o de orden ") porque en el infinito se comporta como . El orden de complejidad (de mayor a menor eficiencia) es: . y entonces: .

Propiedades

Las asignaciones tienen . Una secuencia de instrucciones tiene orden . Si tenemos un if y un else tenemos que comprobar el tiempo que tarda en evaluar la condición, el tiempo que tarda en computar lo que hay dentro del if y lo que hay dentro del else. Cogeremos el máximo de los 3. En un bucle será el número de iteraciones por complejidad de la iteración. Puede ser que sea sumar la suma de todas las iteraciones en el caso de que el tiempo de éstas cambie.

Ejemplo (Algoritmo de selección)

El primer for se hace veces y el segundo depende del primero. Primero se ejecuta veces, luego ,… hasta vez. El total es: .

Ejemplo (MergeSort)

Mergesort(Mitad_izquierda); Mergesort(Mitad_derecha); Combinar;

Como es recursiva hemos de sumar los tiempos: Recurrencia que resolvemos: . Además: etc. Quedan las siguientes ecuaciones:

Si sumamos todas las ecuaciones obtenemos : .

Ejemplo (HeapSort)

Insertar(); . Borrar_Min(); .

Para crear el montículo necesitamos ejecutar veces la inserción y veces borrar mínimo. Así: .

Aplicaciones de Pilas

Notación sufija

Operador tras los operandos: ab3^+c*2/

Notación infija: Operador entre los operandos: ((a+b^3)*c)/2

Notación prefija: Operador antes de los operandos

La notación sufija se utiliza porque no necesitamos paréntesis. Se van buscando los operandos anteriores para operar entre ellos. Por eso se utiliza una pila (se necesita el último operando leído).

Algoritmo

Leemos cada caracter de la expresión.

1. Si es un operando: Apilar.
2. Si es un operador: Desapilar el segundo operando. Desapilamos el primer operando. Aplicamos el operador a dichos operandos. Apilamos el resultado.
3. Cuando no quedan más caracteres: Desapilamos el resultado final, queda una pila vacía.

Ejemplo en hoja.

Cuenta de paréntesis

(((a+b)*c)+d)-5

Algoritmo

Leemos cada caracter de la expresión:

1. Paréntesis de apertura: Apilamos
2. Paréntesis de cierre: Desapilamos
3. Si al terminar la pila está vacía, la cuenta de paréntesis es correcta.

Colas

Las colas son listas enlazadas FIFO (First In-First Out). En una cola los elementos se insertan al final de la lista y se borran del principio de la lista. (Imagen en hoja) ->][][][][->

Estructura del TAD cola

(PNodo y Nodo igual que en cualquier lista enlazada)

typedef struct Nodo * PNodo;
typedef struct Nodo{
    int dato;
    PNodo siguiente;
}Nodo;

typedef struct{
    PNodo principio;
    PNodo final;
}Cola;

(En algunas funciones tendremos que usar punteros, &... y en otras no)

Función crear cola

void crearCola(Cola * C){
    C->principio = NULL;
    C->final = NULL;
}

Función main que reserva memoria

void main(){
    Cola *C;
    C = (Cola *) malloc (sizeof(Cola));
    //Incluir detección de error
    crearCola(C);
}

Función que comprueba si está vacía

int esVacia(Cola C){ //1 si es vacía, 0 sino lo es
    return(C.principio == NULL); //Vale con comprobar que el principio sea NULL
}

Main con esVacia

void main(){
    Cola *C;
    int vacia;
    C = (Cola *) malloc (sizeof(Cola));
    //Incluir detección de error
    crearCola(C);
    vacia = esVacia(*C);
}

Funciones de insertar y borrar (encolar y desencolar)

(Dibujo en hoja)

int encolar(int dato, Cola*C){
    PNodo NodoTemp;
    NodoTemp = (PNodo) malloc (sizeof(Nodo));
    if (NodoTemp == NULL){
        printf("Error de reserva de memoria");
        return 1;
    }
    NodoTemp->dato = dato;
    NodoTemp->siguiente = NULL;
    if(!esVacia(*C))
        C->final->siguiente = NodoTemp;
    else
        C->principio=NodoTemp;
    C->final = NodoTemp;
    return 0;
}

void desencolar(Cola *C){
    if (esVacia(*C)) 
        printf("No se puede desencolar"); //Para cola vacía
    else{
        PNodo NodoTemp;
        NodoTemp = C->principio;
        C->principio = NodoTemp->siguiente;
        if (C->principio ==NULL) //Para cola de un elemento
            C->final = NULL;
        free(NodoTemp);
    }
}

*EJERCICIO*

Escribir una función que devuelva el dato del primer nodo de una cola.

int primero(Cola C){
    if (!esVacia(C))
        return(C.principio->dato);
    printf("La cola está vacía
");
    return -1;
}

void borrarCola (Cola *C){
    if (C->principio == NULL)
        printf("La cola está vacía
");
    else
        while (!esVacia(*C))
            desencolar(C);
    free(C);
}

******** Ejercicio: Función ... imprimirCola(...);

Tipos especiales de colas

Colas circulares

Aquellas en las que el último elemento apunta al primero. Con ellas nos basta con especificar un puntero al último elemento (ya que este apunta al primero).

Colas de doble entrada (bicolas)

Conjunto de elementos a los que se puede añadir o quitar elementos desde cualquiera de los extremos de la cola: Añadir/quitar por el principio y por el final. Como el principio y el final son indiferentes, se pueden definir punteros a "izquierda" y "derecha".

Una bicola con restricción de entrada sólo permite inserciones por uno de los extremos (bien sea izquierdo o derecho).

Una bicola con restricción de salida sólo permite borrados por uno de los extremos.

/*Esto puede caer*/ Funciones crearBicola bicolaVacia insertarIzquierda insertarDerecha borrarIzquierda borrarDerecha borrarBicola imprimirBicola izquierdo derecho