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ística | Significado | Contraejemplo |
|---|---|---|
| Entrada | Tiene cero o más entradas externas | No tener entrada también es válido, como generar números aleatorios |
| Salida | Produce al menos un resultado | Un “algoritmo” sin ninguna salida no tiene sentido |
| Precisión | El significado de cada paso debe ser claro e inequívoco. | Descripciones vagas como “aumentar apropiadamente” no son aceptables |
| Finitud | Debe 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. |
| Viabilidad | Cada 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ímbolo | Significado |
|---|---|
| Rectángulo redondeado (o elipse) | Inicio / Fin |
| Rectángulo | Paso de procesamiento |
| Rombo | Decisión / Bifurcación |
| Paralelogramo | Entrada / Salida |
| Flecha | Direcció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
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ón | Nombre | n=10 | n=1000 | Algoritmo típico |
|---|---|---|---|---|
| O(1) | Orden constante | 1 | 1 | Acceso a arreglo por índice, búsqueda en tabla hash |
| O(log n) | Orden logarítmico | ~3 | ~10 | Búsqueda binaria, operaciones en BST balanceado |
| O(n) | Orden lineal | 10 | 1000 | Búsqueda lineal, recorrido de arreglo |
| O(n log n) | Orden lineal logarítmico | ~30 | ~10000 | Ordenamiento por mezcla (merge sort), ordenamiento rápido (promedio) |
| O(n²) | Orden cuadrático | 100 | 1000000 | Ordenamiento de burbuja, ordenamiento por selección |
| O(2ⁿ) | Orden exponencial | 1024 | Números astronómicos | Resolver 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
/* 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
/* 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 <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;
}
Otras extensionesErrores 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.