Definición y Representación de Algoritmos

Un algoritmo se define como una secuencia finita, ordenada y precisa de instruccionse diseñadas para resolver un problema específico o realizar una tarea computacional. En términos sencillos, es la metodología paso a paso que una computadora ejecuta para transformar datos de entrada en resultados deseados.

Formas de Representación

• Pseudocódigo: Emplea una estructura similar a los lenguajes de programación pero utilizando lenguaje natural. Facilita la lógica de diseño sin preocuparse por la sintaxis estricta de un compilador.
• Lenguaje Natural: Describe los pasos utilizando lenguaje cotidiano. Aunque es accesible, carece de la rigurosidad necesarai para evitar ambigüedades en la ejecución.
• Diagramas de Flujo: Representación gráfica mediante símbolos estandarizados y flechas que ilustran el flujo de control y las operaciones. Ofrece una visión visual e intuitiva de la lógica.

Propiedades Fundamentales

• Finitud: El algoritmo debe terminar después de un número determinado y finito de pasos. En recursividad, es vital garantizar una condición de salida para evitar bucles infinitos.
• Definición Precisa (Determinismo): Cada instrucción debe ser inequívoca. Para un mismo estado y entrada, el algoritmo debe producir siempre el mismo resultado.
• Factibilidad: Todas las operaciones deben ser lo suficientemente básicas como para poder ejecutarse en un tiempo finito mediante operaciones primitivas.
• Entradas: Cantidades iniciales de datos que el algoritmo toma para operar. Pueden ser cero o más.
• Salidas: Resultados generados a partir de las entradas. Un algoritmo debe producir al menos un valor observable; de lo contrario, carece de utilidad práctica.

Criterios de Evaluación Algorítmica

Al diseñar o seleccionar un algoritmo, se deben considerar los siguientes pilares:

• Corrección: El requisito primordial. El algoritmo debe resolver el problema para todos los casos válidos, pasando desde pruebas básicas hasta casos extremos (casos borde).
• Legibilidad: El código o pseudocódigo debe ser claro para otros desarrolladores, facilitando el mantenimiento, la depuración y la colaboración.
• Robustez: Capacidad de manejar entradas inválidas o situaciones inesperadas sin fallar catastróficamente o generar resultados erróneos silenciosos.
• Generalidad: El algoritmo debe ser aplicable a un conjunto amplio de problemas similares, no solo a un caso altamente específico.
• Eficiencia (Tiempo y Espacio):
  • Tiempo: Rapidez con la que el algoritmo completa su tarea en función del tamaño de los datos.
  • Espacio: Cantidad de memoria auxiliar requerida durante la ejecución.

Ilustración Práctica: Ordenamiento por Selección

A continuación, se muestra la lógica del algoritmo de ordenamiento por selección utilizando diferentes métodos de representación.

Descripción Lógica: El algoritmo divide el conjunto en una parte ordenada y otra desordenada. Busca el elemento mínimo en la sección desordenada y lo intercambia con el primer elemento de dicha sección, expandiendo así la frontera ordenada.

Pseudocódigo:

funcion ordenarSeleccion(coleccion: lista de enteros)
    tamano = longitud(coleccion)
    para indiceActual desde 0 hasta tamano - 1 hacer
        indiceMenor = indiceActual
        para indiceSiguiente desde indiceActual + 1 hasta tamano - 1 hacer
            si coleccion[indiceSiguiente] < coleccion[indiceMenor] entonces
                indiceMenor = indiceSiguiente
        intercambiar(coleccion[indiceActual], coleccion[indiceMenor])
fin funcion

Diagrama de Flujo:

flowchart TD
    Inicio --> A[Inicializar tamano = longitud(coleccion)]
    A --> B[for indiceActual = 0 to tamano-1]
    B --> C[Inicializar indiceMenor = indiceActual]
    C --> D[for indiceSiguiente = indiceActual+1 to tamano-1]
    D --> E{coleccion[indiceSiguiente] < coleccion[indiceMenor]?}
    E -->|Sí| F[Actualizar indiceMenor = indiceSiguiente]
    E -->|No| G[Continuar siguiente iteración]
    F --> G
    G --> D
    D --> H[Intercambiar coleccion[indiceActual] y coleccion[indiceMenor]]
    H --> B
    B --> Fin[Ordenamiento completado]

Análisis de Complejidad Temporal

La métrica principal para evaluar la eficiencia temporal es la complejidad de tiempo. Existen dos enfoques para medirla:

1. Análisis a posteriori (Estadístico): Consiste en ejecutar el programa y medir el tiempo real con un cronómetro. Desventaja: Depende fuertemente del hardware, el lenguaje, el compilador y el sistema operativo, lo que no refleja la eficiencia intrínseca del algoritmo.
2. Análisis a priori (Asintótico): Estima el tiempo de ejecución en función del tamaño de la entrada (n), abstrayéndose de las constantes de hardware. Esto nos lleva al concepto de Notación Big O.

Notación Big O y Casos Comunes

La complejidad temporal T(n) = O(f(n)) describe cómo crece el tiempo de ejecución a medida que n tiende a infinito, enfocándose en el término de mayor crecimiento.

Complejidad Constante O(1):

double calcularAreaTriangulo(double base, double altura) {
    double area = (base * altura) / 2.0;
    return area;
}

Las operaciones se ejecutan una sola vez, independientemente del tamaño de cualquier entrada externa.

Complejidad Lineal O(n):

int encontrarMaximo(int* numeros, int cantidad) {
    int valorMax = numeros[0];
    for (int k = 1; k < cantidad; k++) {
        if (numeros[k] > valorMax) {
            valorMax = numeros[k];
        }
    }
    return valorMax;
}

El bucle itera n veces, por lo que el tiempo crece linealmente con el tamaño del arreglo.

Complejiadd Cuadrática O(n²):

int sumarMatriz(int** matriz, int dimension) {
    int total = 0;
    for (int fila = 0; fila < dimension; fila++) {
        for (int col = 0; col < dimension; col++) {
            total += matriz[fila][col];
        }
    }
    return total;
}

Al tener bucles anidados que dependen de la misma variable n (o dimension), el número de operaciones es n * n.

Comprensión Profunda del Cálculo de Operaciones

La complejidad no mide los segundos exactos, sino la tasa de crecimiento de las operaciones básicas.

#include <stdio.h>

void procesarLotes(int totalLotes) {
    int loteActual = 1;                  // 1 vez
    while (loteActual <= totalLotes) {   // n + 1 veces
        printf("Lote %d procesado\n", loteActual); // n veces
        loteActual++;                    // n veces
    }
    printf("Fin del procesamiento.\n");  // 1 vez
}

int main() {
    procesarLotes(100);
    return 0;
}

Sumando las ejecuciones: T(n) = 1 + (n + 1) + n + n + 1 = 3n + 3. Al aplicar la notación Big O, descartamos las constantes y los términos de menor orden, resultando en O(n).

Cálculo de Complejidad con Múltiples Variables

Cuando hay más de una variable de entrada, ambas deben considerarse en la función de crecimiento.

int filas = 4;
int columnas = 8;
for (int r = 0; r < filas; r++) {
    for (int c = 0; c < columnas; c++) {
        printf("Coordenada: (%d, %d)\n", r, c);
    }
}

El bucle externo se ejecuta f veces y el interno c veces por cada iteración externa. La complejidad total es O(f * c). Si f y c fueran iguales a n, sería O(n²).

Jerarquía de Complejidades Temporales

De menor a mayor costo computacional a medida que n crece:

• O(1): Constante. Acceso a arreglos, operaciones aritméticas básicas.
• O(log n): Logarítmica. Búsqueda binaria. El problema se reduce a la mitad en cada paso.
• O(n): Lineal. Recorridos simples.
• O(n log n): Linealítmica. Algoritmos de ordenamiento eficientes como Merge Sort o Quick Sort.
• O(n²): Cuadrática. Bubble Sort, Insertion Sort, matrices densas.
• O(n³): Cúbica. Multiplicación de matrices ingenua, tres bucles anidados.
• O(2^n): Exponencial. Subconjuntos, recursividad de Fibonacci ingenua.
• O(n!): Factorial. Permutaciones, problema del viajante (fuerza bruta).

Detalle de Complejidades y Ejemplos Refactorizados

Logarítmica O(log n):

void reducirPotencia(int limite) {
    int valor = limite;
    while (valor > 1) {
        valor = valor / 3;
    }
}

En cada iteración, valor se divide por 3. El número de pasos m satisface 3^m = n, por lo tanto, m = log_3(n), que asintóticamente es O(log n).

Linealítmica O(n log n):

void procesamientoMixto(int cantidad) {
    for (int i = 0; i < cantidad; i++) {
        int contador = 1;
        while (contador < cantidad) {
            contador = contador * 2;
        }
    }
}

El bucle externo corre n veces. El bucle interno se ejecuta log_2(n) veces. Total: O(n log n).

Raíz Cuadrada O(sqrt(n)):

void iterarRaiz(int limite) {
    int paso = 1;
    while (paso * paso < limite) {
        paso++;
    }
}

El bucle termina cuando paso^2 >= n, lo que significa que se ejecuta aproximadamente sqrt(n) veces.

Análisis de Complejidad Espacial

La complejidad de espacio S(n) = O(f(n)) cuantifica la memoria auxiliar adicional (excluyendo el espacio ocupado por las propias entradas y el código del programa) que el algoritmo requiere en función del tamaño de entrada n.

Espacio Constante O(1)

El algoritmo utiliza una cantidad fija de memoria, sin importar cuán grande sea la entrada. Conocido como algoritmo in-place o en el lugar.

void intercambiarValores(int* a, int* b) {
    int temporal = *a;
    *a = *b;
    *b = temporal;
}

Solo se asigna una variable entera adicional (temporal), por lo que el espacio auxiliar es constante, O(1).

Espacio Lineal O(n)

La memoria auxiliar requerida crece proporcionalmente al tamaño de la entrada.

void crearCopiaInversa(int* original, int tamano) {
    int* copia = (int*)malloc(tamano * sizeof(int));
    for (int idx = 0; idx < tamano; idx++) {
        copia[idx] = original[tamano - 1 - idx];
    }
    free(copia);
}

Se reserva dinámicamente un arreglo de tamaño n. El espacio auxiliar es O(n).

Impacto de la Recursividad en el Espacio y Tiempo

Las llamadas recursivas consumen espacio en la pila de llamadas (call stack). Cada invocación pendiente añade un marco a la pila.

void conteoRegresivo(int numero) {
    if (numero <= 0) {
        printf("Despegue!\n");
    } else {
        printf("%d\n", numero);
        conteoRegresivo(numero - 1);
    }
}

int main() {
    conteoRegresivo(5);
    return 0;
}

Análisis Temporal: La función se llama a sí misma n veces antes de llegar al caso base. Complejidad temporal: O(n).

Análisis Espacial: Al invocar conteoRegresivo(5), el sistema apila conteoRegresivo(4), luego conteoRegresivo(3), y así sucesivamente hasta llegar a 0. En el punto máximo de profundidad, hay n marcos de pila activos simultáneamente. Por lo tanto, la complejidad espacial también es O(n).