0. Introducción:

1. Esta sección incluye conocimientos complementarios (identificados con "add"), componentes de la STL (identificados con "stl") y estructuras de datos (identificados con "ds").
2. Estas notas registran puntos clave de conocimiento, algunos de los cuales pueden estar incompletos y se complementarán según el progreso del aprendizaje.
3. Algunos conceptos pueden repetirse de secciones anteriores, pero esta repetición ayuda a consolidar el conocimiento.

1. add_Complejidad Temporal:

1.1. Concepto General:

Para un programa con n entradas, analizamos el orden de magnitud del número de operaciones en el peor caso.

• En C++, la complejidad temporal es un indicador fundamental para medir la eficiencia de los algoritmos. Describe cómo cambia el tiempo de ejecución del algoritmo a medida que aumenta el tamaño de la entrada, sin considerar el tiempo específico (que depende del hardware, compilador, etc.).
• La complejidad temporal se representa con la notación O (Big O), enfocándose en la tendencia de crecimiento en el peor caso, ignorando términos constantes y de orden inferior.

1.2. Tipos de Complejidad Temporal:

• O(1): Tiempo constante: Para n entradas, el número de pasos es fijo.

int obtenerPrimerElemento(vector<int>& arr) {
    return arr[0]; // Acceso directo, completado en 1 paso
}

• O(log n): Tiempo logarítmico: Para n entradas, el algoritmo termina después de log n operaciones.
• Característica: En cada iteración, el tamaño del problema se reduce a la mitad (como en la búsqueda binaria).
• Ejemplo de análisis:

Búsqueda binaria

1. Rango inicial: n elementos.
2. Cada iteración: el rango se reduce a la mitad, quedando n/2, n/4, ..., 1.
3. Número de iteraciones: después de log₂n iteraciones, el rango es 1.
4. Conclusión: complejidad temporal de O(log n).

• O(n): Tiempo lineal
• Ejemplo: Recorrer una entrada de n elementos requiere n operaciones.
• O(n log n): Tiempo lineal-logarítmico
• Ejemplo: Común en algoritmos de ordenación eficientes.
• Característica: El problema se descompone en subproblemas de tamaño n con complejidad log n.
• O(n²): Tiempo cuadrático
• Característica: El número de pasos es proporcional al cuadrado de n.
• Ejemplo: Común en bucles anidados.
• Complejidades superiores (O(n³), O(2ⁿ), etc.)
• O(n³): Tres bucles anidados (como multiplicación de matrices).
• O(2ⁿ): Complejidad exponencial, como en la recursión no optimizada de Fibonacci.

1.3. Cómo Analizar la Complejidad Temporal:

1. Contar las iteraciones de bucles: Para bucles anidados, tomar el producto (dos bucles → O(n×m), si n=m entonces O(n²)).
2. Ignorar operaciones constantes: Como declaraciones de variables o condiciones simples que no crecen con n.
3. Enfocarse en el peor caso: Por ejemplo, en la búsqueda lineal, el mejor caso es O(1) (primer elemento coincide), pero la complejidad se considera como O(n) (peor caso).

1.4. Complejidad Espacial:

• Una vez entendida la complejidad temporal, la complejidad espacial es un concepto relacionado.
• Definición: Cantidad de memoria adicional que necesita un algoritmo para ejecutarse.
• Se representa de la misma manera que la complejidad temporal.

2. STL_Gestores de Espacio y Pools de Memoria:

2.1. Gestores de Espacio:

El gestor de espacio es el último de los seis componentes de la STL, responsable de administrar el espacio de memoria que necesitan los contenedores.

• Cada contenedor puede tener un parámetro de gestor de espacio, generalmente el último parámetro de la plantilla. Es un parámetro opcional, por lo que normalmente no se especifica y se utiliza por defecto la clase allocator de la STL como gestor de espacio.

2.2. Pools de Memoria:

En la STL de C++, el pool de memoria es una técnica eficiente de gestión de memoria.

• Los pools de memoria se utilizan principalmente para optimizar la asignación y liberación frecuente de objetos pequeños (como elementos de vector o nodos de listas).
• Razones del diseño de pools de memoria en STL: Cuando los contenedores de STL solicitan y liberan espacio, surge un problema: las estructuras de datos basadas en nodos solicitan/liberan frecuentemente bloques pequeños de memoria. Solicitar directamente del sistema es lento y puede generar fragmentación de memoria, reduciendo la eficiencia del uso de memoria. Por lo tanto, se utilizan pools de memoria para gestionar estas asignaciones/liberaciones pequeñas. El método es sobrecargar los operadores new y delete.
• Gestión de pools de memoria: La STL utiliza una tabla hash para gestionar los pools. Esta tabla contiene cubos (buckets) que son múltiplos de 8, cada uno almacenando espacios de memoria del tamaño correspondiente. Por ejemplo, el cubo de 8 almacena espacios de 8 bytes, el de 32 almacena espacios de 32 bytes, etc. En la STL, se usa 128 bytes como línea divisoria: espacios mayores a 128 bytes se consideran grandes y se solicitan directamente del sistema, mientras que espacios ≤ 128 bytes son gestionados por el pool de memoria. Para la gestión, el pool se divide: si un nodo necesita espacio, se divide del pool un espacio del tamaño del nodo (con previsión de posibles necesidades futuras de espacios similares) y se coloca en el cubo correspondiente. Cuando un nodo se libera, el espacio se devuelve al cubo correspondiente para su reutilización.
• En la STL, el gestor de espacio que solicita/libera directamente del sistema se llama gestor de espacio de primer nivel, mientras que el que gestiona pools de memoria se llama gestor de espacio de segundo nivel.

3. ds_Resumen de Algoritmos de Ordenación:

★★ Todos los algoritmos de ordenación se pueden entender primero considerando el principio de ordenación con secuencias pequeñas de 3 o 4 elementos, luego generalizando para escribir el código.

3.1. Ordenación por Burbuja:

• Principio de ordenación:
• Código:

void ordenacionBurbuja(vector<int>& arr)
{
    int n = arr.size();
    int i, j, temp;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

• Análisis de complejidad temporal: O(n²)
• Bucle exterior: se ejecuta n veces (i=0 a i=n-1)
• Bucle interior: en la i-ésima iteración se realizan n-1-i comparaciones
• [(n-1) + (n-2) + … + 1 = n(n-1)/2 ≈ O(n²)]
• Análisis de ventajas y desventaajs:
• Ventajas: simple e intuitivo, ordenación in situ.
• Desventajas: alta complejidad temporal.

3.2. Ordenación por Selección:

• Principio de ordenación:
• Código:

void ordenacionSeleccion(vector<int>& arr)
{
    int i, j, max_idx = 0;
    for (i = 0; i < arr.size()-1; i++)
    {
        max_idx = 0;
        for (j = 1; j < arr.size()-i; j++)
        {
            if (arr[j] > arr[max_idx])
            {
                max_idx = j;
            }
        }
        swap(arr[max_idx], arr[arr.size() - i - 1]);
    }
}

• Análisis de complejidad temporal: O(n²)
• Bucle exterior: se ejecuta n-1 veces (i=0 a i=n-2)
• Bucle interior: en la i-ésima iteración se realizan n-1-i comparaciones
• [(n-1) + (n-2) + … + 1 = n(n-1)/2 ≈ O(n²)]
• Análisis de ventajas y desventajas:
• Ventajas: simple e intuitivo, sin espacio adicional.
• Desventajas: alta complejidad temporal.

3.3. Ordenación por Inserción:

• Principio de ordenación:
• Código:

void ordenacionInsercion(vector<int>& arr)
{
    int ordenado = 0;  // Índice final de la secuencia ordenada
    int actual = 1;    // Índice del elemento a comparar en la secuencia no ordenada
    int i, j;
    for (i = actual; i < arr.size(); i++)
    {
        for (j = ordenado; j >= 0; j--)
        {
            if (arr[j] > arr[actual])
            {
                swap(arr[actual], arr[j]);
                actual = j;
            }
        }
        ++ordenado;
        actual = i + 1;
    }
}

• Análisis de complejidad temporal: O(n²)
• Peor caso (array en orden inverso):
• Cada inserción requiere comparar con todos los elementos ya ordenados
• La k-ésima inserción requiere k comparaciones
• Total de comparaciones = 1+2+…+(n-1) = n(n-1)/2 → O(n²)
• Análisis de ventajas y desventajas:
• Ventajas: simple e intuitivo, sin espacio adicional.
• Desventajas: alta complejidad temporal.

3.4. Ordenación por Montículo:

• Principio de ordenación:
• Código:

// Ordenación por montículo (usando montículo máximo)
// Función de monticulización: solo garantiza que cada raíz sea mayor que sus hijos,
// pero para llevar el máximo a la raíz, se debe empezar desde las hojas
void heapify(vector<int>& arr, int n)
{
    // Nodo con dos hijos
    if (2 * n + 1 < arr.size() && 2 * n + 2 < arr.size())
    {
        if (arr[n] < arr[2 * n + 1] || arr[n] < arr[2 * n + 2])
        {
            if (arr[2 * n + 1] > arr[2 * n + 2])
            {
                swap(arr[n], arr[2 * n + 1]);
                heapify(arr, 2 * n + 1);
            }
            else
            {
                swap(arr[n], arr[2 * n + 2]);
                heapify(arr, 2 * n + 2);
            }
        }
    }
    // Nodo con un hijo
    else if (2 * n + 1 < arr.size())
    {
        if (arr[n] < arr[2 * n + 1])
        {
            swap(arr[n], arr[2 * n + 1]);
        }
    }
}

void ordenacionMonticulo(vector<int>& arr)
{
    // Construir montículo (reorganizar el array)
    for (int i = arr.size() / 2 - 1; i >= 0; i--)
        heapify(arr, i);
    
    // Extraer elementos uno por uno del montículo
    for (int i = arr.size() - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);  // Mover raíz actual al final
        heapify(arr, 0);       // Heapify el elemento reducido
    }
}

• Análisis de complejidad temporal: O(n log n)
• Construcción del montículo: O(n)
• Extracción de elementos: n veces heapify, cada O(log n)
• Total: O(n) + O(n log n) = O(n log n)
• Análisis de ventajas y desventajas:
• Ventajas: complejidad O(n log n), ordenación in situ.
• Desventajas: no estable, puede ser más complejo de implementar.