Fundamentos de algoritmos

Un algoritmo es una secuencia definida y finita de pasos para resolver un problema específico.

Comprender los conceptos básicos de los algoritmos y los métodos de análisis de eficiencia es un requisito importante para aprender estructuras de datos y algoritmos.


Definición y características de los algoritmos

En ciencias de la computación, un algoritmo es una secuencia finita de instrucciones, donde cada instrucción representa una o más operaciones.

Un algoritmo calificado debe poseer las siguientes cinco características básicas:

CaracterísticaSignificadoContraejemplo
EntradaTiene cero o más entradas externasNo tener entrada también es válido, como generar números aleatorios
SalidaProduce al menos un resultadoUn “algoritmo” sin ninguna salida no tiene sentido
PrecisiónEl significado de cada paso debe ser claro e inequívoco.Descripciones vagas como “aumentar apropiadamente” no son aceptables
FinitudDebe terminar en un número finito de pasos; no puede tener bucles infinitos.El sistema operativo en sí no es un algoritmo, ya que teóricamente se ejecuta indefinidamente.
ViabilidadCada paso se puede realizar mediante operaciones básicas.Dividir por cero no es viable, y “completar la ordenación en un solo paso” tampoco es viable.

La “finitud” de un algoritmo no contradice el “bucle infinito” de un programa. Un programa puede caer en un bucle infinito debido a un bug, pero el algoritmo en sí debe poder terminar en un número finito de pasos. La diferencia es que el algoritmo es un concepto a nivel de “intención de diseño”, mientras que el programa es un concepto a nivel de “ejecución real”.


Métodos de representación de algoritmos

Al diseñar y comunicar algoritmos, se utilizan comúnmente dos formas de representación.

Pseudo-código (Pseudocode)

El pseudo-código utiliza texto cercano al lenguaje natural, pero con un cierto formato estructurado, para describir la lógica del algoritmo.

No depende de la sintaxis de un lenguaje de programación específico, lo que facilita expresar ideas rápidamente.

Por ejemplo, el pseudo-código para encontrar el valor máximo en un conjunto de números:

算法:FindMax
输入:数组 A,长度 n
输出:A 中的最大值

1. max = A[0]
2. for i = 1 to n-1:
3.     if A[i] > max:
4.         max = A[i]
5. return max

Diagrama de flujo (Flowchart)

El diagrama de flujo muestra de manera gráfica e intuitiva el flujo de ejecución del algoritmo.

La figura anterior muestra el flujo de ejecución completo del algoritmo FindMax: comienza con el arreglo de entrada, inicializa el valor máximo actual, luego compara cada elemento sucesivamente, si encuentra un valor mayor actualiza el máximo, y tras completar el recorrido produce el resultado.

Convenciones de símbolos en el diagrama de flujo:

Forma del símboloSignificado
Rectángulo redondeado (o elipse)Inicio / Fin
RectánguloPaso de procesamiento
RomboDecisión / Bifurcación
ParalelogramoEntrada / Salida
FlechaDirección del flujo

Análisis de eficiencia de algoritmos

Después de diseñar un algoritmo, también es necesario evaluar su eficiencia. Esto se mide principalmente en dos dimensiones.

Complejidad temporal

La complejidad temporal describe la tendencia de crecimiento del número de operaciones básicas necesarias para ejecutar el algoritmo a medida que aumenta el tamaño de entrada n.

Observe que nos interesa la “tendencia de crecimiento”, no el “número exacto de ejecuciones”. Porque para entradas a gran escala, la diferencia de un factor constante es mucho menos importante que la diferencia en la tendencia de crecimiento.

Complejidad espacial

La complejidad espacial describe la tendencia de crecimiento de la memoria adicional necesaria durante la ejecución del algoritmo a medida que aumenta el tamaño de entrada n.

Aquí se enfatiza el espacio “adicional”, que se refiere a cuánto espacio auxiliar necesita el algoritmo, aparte de almacenar los propios datos de entrada.

El tiempo y el espacio a menudo forman una contradicción: intercambiar espacio por tiempo, o tiempo por espacio, es una estrategia común de compensación en el diseño de algoritmos. Por ejemplo: una tabla hash intercambia espacio de almacenamiento adicional por un tiempo de búsqueda de O(1); mientras que un algoritmo de ordenación in situ evita el consumo de espacio adicional a costa de unos pocos pasos de cálculo más.


Notación Big O

Notación Big O (Big O Notation)Es la herramienta matemática más utilizada para medir la complejidad temporal y la complejidad espacial.

Describe el límite superior de la tendencia de crecimiento del tiempo de ejecución o del uso de espacio, en el peor caso, a medida que el tamaño de entrada n aumenta.

Definición: si existen constantes positivas c y n0 tales que cuando n ≥ n0, siempre se cumple T(n) ≤ c × f(n), entonces se escribeT(n) = O(f(n))。

En términos sencillos: la notación Big O ignora los factores constantes y los términos de menor orden, y solo se centra en el término de mayor crecimiento.

Por ejemplo: si un algoritmo necesita 3n² + 100n + 500 operaciones, cuando n es suficientemente grande, el término n² domina el crecimiento, por lo que decimos que es O(n²).

Niveles de complejidad comunes

大 O 复杂度增长趋势对比图

La figura anterior muestra intuitivamente la tendencia de cambio de cada nivel de complejidad a medida que crece el tamaño de entrada n.

NotaciónNombren=10n=1000Algoritmo típico
O(1)Orden constante11Acceso a arreglo por índice, búsqueda en tabla hash
O(log n)Orden logarítmico~3~10Búsqueda binaria, operaciones en BST balanceado
O(n)Orden lineal101000Búsqueda lineal, recorrido de arreglo
O(n log n)Orden lineal logarítmico~30~10000Ordenamiento por mezcla (merge sort), ordenamiento rápido (promedio)
O(n²)Orden cuadrático1001000000Ordenamiento de burbuja, ordenamiento por selección
O(2ⁿ)Orden exponencial1024Números astronómicosResolver problemas de subconjuntos por fuerza bruta

Como se puede ver en la tabla, cuando n=1000, O(1) aún requiere solo 1 operación, O(n) requiere 1000, y O(n²) requiere un millón.

En escenarios de datos a gran escala, elegir un algoritmo con la complejidad adecuada puede suponer diferencias de rendimiento de varios órdenes de magnitud.

En la programación práctica, se debe procurar que la complejidad de los algoritmos centrales no supere O(n log n). Cuando la complejidad alcanza O(n²) o más, hay que prestar especial atención a si el tamaño de entrada es manejable y si existen alternativas mejores.


Ejemplo de cálculo de complejidad temporal

El siguiente es un fragmento de código en C y su análisis de complejidad temporal:

Ejemplo

#include <stdio.h>

/* Función: calcula la suma de los elementos de un arreglo
Complejidad temporal: O(n)
n es la longitud del arreglo, el bucle se ejecuta n veces, cada iteración realiza un número constante de operaciones */

int sumArray(int arr[], int n) {
    int total = 0;           /* O(1) — operación de asignación, se ejecuta 1 vez */
    for (int i = 0; i < n; i++) {  /* Cuerpo del bucle */
        total += arr[i];    /* O(1) — suma y asignación, se ejecutan n veces */
    }
    return total;            /* O(1) — operación de retorno, se ejecuta 1 vez */
}
/* Complejidad temporal total: O(1 + n + 1) = O(n)
Los términos constantes de menor orden se ignoran */


int main() {
    int nums[] = {5, 10, 15, 20, 25};
    int size = sizeof(nums) / sizeof(nums[0]);
    int result = sumArray(nums, size);
    printf("Suma de los elementos del arreglo: %d\n", result);  /* Salida: Suma de los elementos del arreglo: 75 */
    return 0;
}

Veamos otro ejemplo con bucles anidados:

Ejemplo

#include <stdio.h>

/* Función: imprime la tabla de multiplicar de n×n
Complejidad temporal: O(n²)
El bucle externo se ejecuta n veces, el bucle interno n veces, total n×n veces */

void printMulTable(int n) {
    for (int i = 1; i <= n; i++) {      /* Bucle externo O(n) */
        for (int j = 1; j <= n; j++) {  /* Bucle interno O(n), después del anidamiento el total es n² */
            printf("%d\t", i * j);      /* Operación O(1) */
        }
        printf("\n");
    }
}
/* Complejidad temporal total: O(n × n) = O(n²) */

int main() {
    printMulTable(5);  /* Imprime la tabla de multiplicar de 5×5 */
    return 0;
}

Ejemplo de cálculo de complejidad espacial

La complejidad espacial se centra en la memoria adicional asignada durante la ejecución del algoritmo.

Ejemplo

#include <stdio.h>
#include <stdlib.h> /* Archivo de cabecera donde se encuentran malloc/free */

/* Función: crea un nuevo arreglo que almacena los valores al cuadrado del arreglo original
Complejidad espacial: O(n) — se asigna un nuevo arreglo de longitud n */

int* squareArray(int arr[], int n) {
    int* result = (int*)malloc(n * sizeof(int));  /* Se asigna espacio adicional para n ints */
    if (result == NULL) {
        return NULL;  /* Si malloc falla, devuelve NULL */
    }
    for (int i = 0; i < n; i++) {
        result[i] = arr[i] * arr[i];
    }
    return result;
}
/* Complejidad espacial O(n):
- El arreglo de entrada arr no se cuenta (pertenece a la entrada en sí)
- El arreglo result asigna adicionalmente n ints, este es el espacio adicional
- La variable i es espacio constante O(1), dominado por O(n) */


int main() {
    int nums[] = {1, 2, 3, 4, 5};
    int n = 5;
    int* squared = squareArray(nums, n);
    if (squared != NULL) {
        for (int i = 0; i < n; i++) {
            printf("%d ", squared[i]);  /* Salida: 1 4 9 16 25 */
        }
        printf("\n");
        free(squared);  /* Liberar manualmente la memoria asignada dinámicamente */
    }
    return 0;
}

Errores comunes de principiantes: la complejidad temporal y espacial analizan la "tendencia de crecimiento" en lugar de valores exactos. Los coeficientes constantes, los términos de orden inferior y las diferencias entre lenguajes de programación son ignorados por la notación O grande. Por lo tanto, O(2n) y O(n) son equivalentes: ambos representan crecimiento lineal.

Otras extensiones