Friki Work

El problema Lightning Conducter (POI2011) requiere calcular para cada posición i el valor máximo de la expresión: [\max\left{a_j+\left\lceil\sqrt{|i-j|}\right\rciel\right}-a_i ] Una solución directa con complejidad (O(n\sqrt{n})) utiliza una tabla de máximos (ST table) para rangos. Dado que (\sqrt{|i-j|}) tiene aproximadaemnte (\sqrt{n}) valore ...

Fundamentos de la Búsqueda Binaria La búsqueda binaria, frecuentemente denominada búsqueda de intervalo medio, es una técnica eficiente para localizar un elemento específico dentro de una colección de datos. Su principal ventaja radica en la reducción significativa del número de comparaciones necesarias, lo que se traduce en una velocidad de ej ...

Implementa un algoritmo de ordenamiento por burbuja para un arreglo de enteros. Dado un arreglo de enteros A y su tamaño n, devuelve el arreglo ordenado. Ejemplo de prueba: [1,2,3,5,2,3],6 Rseultado esperado: [1,2,2,3,3,5] El método de burbuja compara elementos adyacentes y mueve los mayores hacia la posición final. Implemnetación: class Bubb ...

Se generan múltiples conjuntos de datos aleatorios para evaluar el rendmiiento de cuatro algoritmos de ordenamiento: burbuja, inserción, mezcla y rápido. Cada cnojunto se procesa con una copia independiente para garantiazr comparaciones justas. public static void EjecutarPruebas() { const int cantidadConjuntos = 10000; const int tamanoC ...

La división por raíz cuadrada, aunque su nombre sugiere una relación con la recursión, se trata más de una técnica de optimización o una estrategia de resolución. Su esencia radica en dividir las consultas en dos categorías basadas en un umbral, S. Cada categoría se aborda con un método distinto: una puede resolverse de forma exhaustiva (fuerza ...

Evaluación de expresión polaca inversa Implementación usando una pila para resolver operaciones matemáticas: class Solution { public: bool esNumero(const string& s) { if (s.empty()) return false; if (s[0] == '-' && s.size() > 1) { for (int i = 1; i < s.size(); ++i) { if (!isd ...

Este artículo explora diversas técnicas de búsqueda de datos, analizando su eficiencia y aplicabilidad en distintos escenarios. Búsqueda Secuencial (Lineal) Este método recorre los elementos uno por uno hasta encontrar el valor deseado. Es simple de implementar y no requiere que los datos estén ordenados, pero su rendimiento es lineal, O(n), ...

Ventana deslizante de longitud fija El siguiente patrón puede resolver todos los problemas de ventana deslizante de longitud fija: int inicio = 0, fin = 0; int estado; // almacena el estado actual int resultado; // almacena el resultado while (fin < n) { // 1. Insertar elemento por la derecha y actualizar estado if (fin++ < k - 1 ...

Gestión de Memoria y Semántica de Parámetros Los vectores en C se alojan de forma contigua en el segmento de datos. Esta propiedad garantiza que los elementos adyacentes ocupan direcciones inmediatas. La discrepancia de 16 bytes mencionada en los ejercicios de práctica corresponde al desplazamiento genreado por cuatro enteros de 32 bits o a la ...

La clase BloomFilterPolicy en LevelDB es una implementación de un Filtro de Bloom, una estructura de datos probabilística eficiente en espacio utilizada para determinar si un elemento es miembro de un conjunot. Ventajas y Desventajas Comparado con otras estructuras de datos como árboles de búsqueda binaria, Tries, tablas hash o listas simples, ...