c++ - online - complejidad de algoritmos pdf

Algoritmo O(N) más lento que el algoritmo O(N logN) (6)

En un conjunto de números, cada número aparece incluso una cantidad de veces, y solo un número aparece como número impar de veces. Necesitamos encontrar ese número (la pregunta fue discutida previamente en Desbordamiento de pila ).

Aquí hay una solución que resuelve la pregunta con 3 métodos diferentes: dos métodos son O (N) (hash_set y hash_map), mientras que uno es O (NlogN) (clasificación). Sin embargo, la creación de perfiles para entradas arbitrariamente grandes muestra que la clasificación es más rápida y se vuelve más y más rápida (en comparación) a medida que aumenta la entrada.

¿Qué hay de malo con la implementación o el análisis de complejidad? ¿Por qué el método O (NlogN) es más rápido?

#include <algorithm> #include <chrono> #include <cmath> #include <iostream> #include <functional> #include <string> #include <vector> #include <unordered_set> #include <unordered_map> using std::cout; using std::chrono::high_resolution_clock; using std::chrono::milliseconds; using std::endl; using std::string; using std::vector; using std::unordered_map; using std::unordered_set; class ScopedTimer { public: ScopedTimer(const string& name) : name_(name), start_time_(high_resolution_clock::now()) {} ~ScopedTimer() { cout << name_ << " took " << std::chrono::duration_cast<milliseconds>( high_resolution_clock::now() - start_time_).count() << " milliseconds" << endl; } private: const string name_; const high_resolution_clock::time_point start_time_; }; int find_using_hash(const vector<int>& input_data) { unordered_set<int> numbers(input_data.size()); for(const auto& value : input_data) { auto res = numbers.insert(value); if(!res.second) { numbers.erase(res.first); } } return numbers.size() == 1 ? *numbers.begin() : -1; } int find_using_hashmap(const vector<int>& input_data) { unordered_map<int,int> counter_map; for(const auto& value : input_data) { ++counter_map[value]; } for(const auto& map_entry : counter_map) { if(map_entry.second % 2 == 1) { return map_entry.first; } } return -1; } int find_using_sort_and_count(const vector<int>& input_data) { vector<int> local_copy(input_data); std::sort(local_copy.begin(), local_copy.end()); int prev_value = local_copy.front(); int counter = 0; for(const auto& value : local_copy) { if(prev_value == value) { ++counter; continue; } if(counter % 2 == 1) { return prev_value; } prev_value = value; counter = 1; } return counter == 1 ? prev_value : -1; } void execute_and_time(const string& method_name, std::function<int()> method) { ScopedTimer timer(method_name); cout << method_name << " returns " << method() << endl; } int main() { vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28}); for(const auto& input_size : input_size_vec) { // Prepare input data std::vector<int> input_data; const int magic_number = 123454321; for(int i=0;i<input_size;++i) { input_data.push_back(i); input_data.push_back(i); } input_data.push_back(magic_number); std::random_shuffle(input_data.begin(), input_data.end()); cout << "For input_size " << input_size << ":" << endl; execute_and_time("hash-set:",std::bind(find_using_hash, input_data)); execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, input_data)); execute_and_time("hash-map:",std::bind(find_using_hashmap, input_data)); cout << "--------------------------" << endl; } return 0; }

Resultados de perfiles:

sh$ g++ -O3 -std=c++11 -o main *.cc sh$ ./main For input_size 262144: hash-set: returns 123454321 hash-set: took 107 milliseconds sort-and-count: returns 123454321 sort-and-count: took 37 milliseconds hash-map: returns 123454321 hash-map: took 109 milliseconds -------------------------- For input_size 1048576: hash-set: returns 123454321 hash-set: took 641 milliseconds sort-and-count: returns 123454321 sort-and-count: took 173 milliseconds hash-map: returns 123454321 hash-map: took 731 milliseconds -------------------------- For input_size 4194304: hash-set: returns 123454321 hash-set: took 3250 milliseconds sort-and-count: returns 123454321 sort-and-count: took 745 milliseconds hash-map: returns 123454321 hash-map: took 3631 milliseconds -------------------------- For input_size 16777216: hash-set: returns 123454321 hash-set: took 14528 milliseconds sort-and-count: returns 123454321 sort-and-count: took 3238 milliseconds hash-map: returns 123454321 hash-map: took 16483 milliseconds -------------------------- For input_size 268435456: hash-set: returns 123454321 hash-set: took 350305 milliseconds sort-and-count: returns 123454321 sort-and-count: took 60396 milliseconds hash-map: returns 123454321 hash-map: took 427841 milliseconds --------------------------

Adición

La solución rápida con xor sugerida por @Matt está, por supuesto, fuera del concurso: menos de 1 segundo para el peor de los casos, por ejemplo:

int find_using_xor(const vector<int>& input_data) { int output = 0; for(const int& value : input_data) { output = output^value; } return output; } For input_size 268435456: xor: returns 123454321 xor: took 264 milliseconds

pero la pregunta sigue en pie: ¿por qué el hash es tan ineficiente en comparación con la clasificación en la práctica a pesar de la ventaja de la complejidad algorítmica teórica?

Comencemos mirando los números para la solución de clasificación. En la tabla a continuación, la primera columna es la relación de tamaño. Se calcula calculando NlogN para una prueba determinada y dividiendo por NlogN para la primera prueba. La segunda columna es la relación de tiempo entre una prueba dada y la primera prueba.

NlogN size ratio time ratio 4*20/18 = 4.4 173 / 37 = 4.7 16*22/18 = 19.6 745 / 37 = 20.1 64*24/18 = 85.3 3238 / 37 = 87.5 1024*28/18 = 1590 60396 / 37 = 1630

Puede ver que hay una muy buena concordancia entre las dos proporciones, lo que indica que la rutina de clasificación es de hecho O (NlogN) .

Entonces, ¿por qué las rutinas hash no funcionan como se esperaba? Simple, la noción de que extraer un elemento de una tabla hash es O (1) es pura fantasía. El tiempo real de extracción depende de la calidad de la función hashing y del número de bins en la tabla hash. El tiempo real de extracción va de O (1) a O (N) , donde el peor de los casos ocurre cuando todas las entradas en la tabla hash terminan en el mismo contenedor. Por lo tanto, si utiliza una tabla hash, debe esperar que su rendimiento esté entre O (N) y O (N ^ 2), lo que parece ajustarse a sus datos, como se muestra a continuación.

O(N) O(NlogN) O(N^2) time 4 4.4 16 6 16 20 256 30 64 85 4096 136 1024 1590 10^6 3274

Tenga en cuenta que la relación de tiempo está en el extremo inferior del rango, lo que indica que la función de almohadilla funciona bastante bien.

Ejecuté el programa a través de valgrind con diferentes tamaños de entrada, y obtuve estos resultados para recuentos de ciclos:

with 1<<16 values: find_using_hash: 27 560 872 find_using_sort: 17 089 994 sort/hash: 62.0% with 1<<17 values: find_using_hash: 55 105 370 find_using_sort: 35 325 606 sort/hash: 64.1% with 1<<18 values: find_using_hash: 110 235 327 find_using_sort: 75 695 062 sort/hash: 68.6% with 1<<19 values: find_using_hash: 220 248 209 find_using_sort: 157 934 801 sort/hash: 71.7% with 1<<20 values: find_using_hash: 440 551 113 find_using_sort: 326 027 778 sort/hash: 74.0% with 1<<21 values: find_using_hash: 881 086 601 find_using_sort: 680 868 836 sort/hash: 77.2% with 1<<22 values: find_using_hash: 1 762 482 400 find_using_sort: 1 420 801 591 sort/hash: 80.6% with 1<<23 values: find_using_hash: 3 525 860 455 find_using_sort: 2 956 962 786 sort/hash: 83.8%

Esto indica que el tiempo de ordenación está superando lentamente el tiempo hash, al menos teóricamente. Con mi compilador / biblioteca particular (gcc 4.8.2 / libsddc ++) y la optimización (-O2), los métodos de clasificación y hash serían de la misma velocidad con alrededor de 2 ^ 28 valores, lo que está al límite de lo que estás intentando. Sospecho que otros factores del sistema entran en juego cuando se utiliza esa cantidad de memoria, lo que dificulta la evaluación en el tiempo real de pared.

El hecho de que O(N) fuera aparentemente más lento que O(N logN) me estaba volviendo loco, así que decidí profundizar en el problema.

Hice este análisis en Windows con Visual Studio, pero apuesto a que los resultados serían muy similares en Linux con g ++.

En primer lugar, utilicé Very Sleepy para encontrar las piezas de código que más se ejecutan durante el ciclo for en find_using_hash() . Esto es lo que vi:

Como puede ver, las entradas superiores están todas relacionadas con las listas (se llama a RtlAllocateHeap desde el código de la lista). Aparentemente, el problema es que para cada inserción en el conjunto unordered_set y dado que los segmentos se implementan como listas, se realiza una asignación para un nodo y esto dispara la duración del algoritmo, en oposición al tipo que no hace asignaciones.

Para estar seguro de que este era el problema, escribí una implementación MUY simple de una tabla hash sin asignaciones, y los resultados fueron mucho más razonables:

Así que ahí está, el factor log N multiplicando N que en su ejemplo más grande (es decir, 1<<28 ) es 28, es aún más pequeño que la cantidad "constante" de trabajo requerida para una asignación.

Este análisis es sustancialmente el mismo que el realizado por el user3386199 en su answer . Es el análisis que habría realizado independientemente de su respuesta, pero él llegó primero.

Ejecuté el programa en mi máquina (HP Z420 con un derivado de Ubuntu 14.04 LTE) y agregué una salida para 1<<26 , así que tengo un conjunto diferente de números, pero las proporciones son notablemente similares a las proporciones de los datos en el publicación original. Los tiempos crudos que obtuve fueron (archivo on-vs-logn.raw.data ):

For input_size 262144: hash-set: returns 123454321 hash-set: took 45 milliseconds sort-and-count: returns 123454321 sort-and-count: took 34 milliseconds hash-map: returns 123454321 hash-map: took 61 milliseconds -------------------------- For input_size 1048576: hash-set: returns 123454321 hash-set: took 372 milliseconds sort-and-count: returns 123454321 sort-and-count: took 154 milliseconds hash-map: returns 123454321 hash-map: took 390 milliseconds -------------------------- For input_size 4194304: hash-set: returns 123454321 hash-set: took 1921 milliseconds sort-and-count: returns 123454321 sort-and-count: took 680 milliseconds hash-map: returns 123454321 hash-map: took 1834 milliseconds -------------------------- For input_size 16777216: hash-set: returns 123454321 hash-set: took 8356 milliseconds sort-and-count: returns 123454321 sort-and-count: took 2970 milliseconds hash-map: returns 123454321 hash-map: took 9045 milliseconds -------------------------- For input_size 67108864: hash-set: returns 123454321 hash-set: took 37582 milliseconds sort-and-count: returns 123454321 sort-and-count: took 12842 milliseconds hash-map: returns 123454321 hash-map: took 46480 milliseconds -------------------------- For input_size 268435456: hash-set: returns 123454321 hash-set: took 172329 milliseconds sort-and-count: returns 123454321 sort-and-count: took 53856 milliseconds hash-map: returns 123454321 hash-map: took 211191 milliseconds -------------------------- real 11m32.852s user 11m24.687s sys 0m8.035s

awk.analysis.sh un script, awk.analysis.sh , para analizar los datos:

#!/bin/sh awk '' BEGIN { printf("%9s %8s %8s %8s %8s %8s %8s %9s %9s %9s %9s/n", "Size", "Sort Cnt", "R:Sort-C", "Hash Set", "R:Hash-S", "Hash Map", "R:Hash-M", "O(N)", "O(NlogN)", "O(N^3/2)", "O(N^2)") } /input_size/ { if (old_size == 0) old_size = $3; size = $3 } /hash-set: took/ { if (o_hash_set == 0) o_hash_set = $3; t_hash_set = $3 } /sort-and-count: took/ { if (o_sort_cnt == 0) o_sort_cnt = $3; t_sort_cnt = $3 } /hash-map: took/ { if (o_hash_map == 0) o_hash_map = $3; t_hash_map = $3 } /^----/ { o_n = size / old_size o_nlogn = (size * log(size)) / (old_size * log(old_size)) o_n2 = (size * size) / (old_size * old_size) o_n32 = (size * sqrt(size)) / (old_size * sqrt(old_size)) r_sort_cnt = t_sort_cnt / o_sort_cnt r_hash_map = t_hash_map / o_hash_map r_hash_set = t_hash_set / o_hash_set printf("%9d %8d %8.2f %8d %8.2f %8d %8.2f %9.0f %9.2f %9.2f %9.0f/n", size, t_sort_cnt, r_sort_cnt, t_hash_set, r_hash_set, t_hash_map, r_hash_map, o_n, o_nlogn, o_n32, o_n2) }'' < on-vs-logn.raw.data

La salida del programa es bastante amplia, pero da:

Size Sort Cnt R:Sort-C Hash Set R:Hash-S Hash Map R:Hash-M O(N) O(NlogN) O(N^3/2) O(N^2) 262144 34 1.00 45 1.00 61 1.00 1 1.00 1.00 1 1048576 154 4.53 372 8.27 390 6.39 4 4.44 8.00 16 4194304 680 20.00 1921 42.69 1834 30.07 16 19.56 64.00 256 16777216 2970 87.35 8356 185.69 9045 148.28 64 85.33 512.00 4096 67108864 12842 377.71 37582 835.16 46480 761.97 256 369.78 4096.00 65536 268435456 53856 1584.00 172329 3829.53 211191 3462.15 1024 1592.89 32768.00 1048576

Está razonablemente claro que en esta plataforma, los algoritmos hash set y hash map no son O (N), ni tan buenos como O (N.logN), pero son mejores que O (N ^3/2 ) y mucho menos O (N ² ). Por otro lado, el algoritmo de clasificación está muy cerca de O (N.logN) de hecho.

Solo puede atribuirlo a una deficiencia teórica en el conjunto de hash y el código de mapa hash, o un tamaño inadecuado de las tablas hash para que utilicen un tamaño de tabla hash no óptimo. Valdría la pena investigar qué mecanismos existen para preasignar el conjunto de hash y el mapa de hash para ver si el uso afecta el rendimiento. (Consulte también información adicional a continuación).

Y, solo para el registro, aquí está el resultado del script de análisis sobre los datos originales:

Size Sort Cnt R:Sort-C Hash Set R:Hash-S Hash Map R:Hash-M O(N) O(NlogN) O(N^3/2) O(N^2) 262144 37 1.00 107 1.00 109 1.00 1 1.00 1.00 1 1048576 173 4.68 641 5.99 731 6.71 4 4.44 8.00 16 4194304 745 20.14 3250 30.37 3631 33.31 16 19.56 64.00 256 16777216 3238 87.51 14528 135.78 16483 151.22 64 85.33 512.00 4096 268435456 60396 1632.32 350305 3273.88 427841 3925.15 1024 1592.89 32768.00 1048576

Pruebas adicionales muestran que se modifican las funciones hash como se muestra:

int find_using_hash(const vector<int>& input_data) { unordered_set<int> numbers; numbers.reserve(input_data.size());

int find_using_hashmap(const vector<int>& input_data) { unordered_map<int,int> counter_map; counter_map.reserve(input_data.size());

produce un análisis como este:

Size Sort Cnt R:Sort-C Hash Set R:Hash-S Hash Map R:Hash-M O(N) O(NlogN) O(N^3/2) O(N^2) 262144 34 1.00 42 1.00 80 1.00 1 1.00 1.00 1 1048576 155 4.56 398 9.48 321 4.01 4 4.44 8.00 16 4194304 685 20.15 1936 46.10 1177 14.71 16 19.56 64.00 256 16777216 2996 88.12 8539 203.31 5985 74.81 64 85.33 512.00 4096 67108864 12564 369.53 37612 895.52 28808 360.10 256 369.78 4096.00 65536 268435456 53291 1567.38 172808 4114.48 124593 1557.41 1024 1592.89 32768.00 1048576

Claramente, reservar el espacio para el mapa hash es beneficioso.

El código del conjunto hash es bastante diferente; agrega un elemento aproximadamente la mitad del tiempo (total), y ''agrega'' y luego elimina un elemento la otra mitad del tiempo. Esto es más trabajo que el código de mapa hash tiene que hacer, por lo que es más lento. Esto también significa que el espacio reservado es más grande de lo realmente necesario y puede explicar el rendimiento degradado con el espacio reservado.

Realmente depende de la implementación de hash_map / hash_set. Al reemplazar el comando unordered_{map,set} libstdc ++ con dense_hash_{map,set} Google, es significativamente más rápido que el sort . El inconveniente de dense_hash_xxx es que requieren que haya dos valores para la clave que nunca se utilizarán. Ver su documento para más detalles.

Otra cosa que hay que recordar es que hash_{map,set} generalmente realiza una gran cantidad de asignaciones / desasignaciones dinámicas de memoria, por lo que es mejor usar una alternativa mejor al malloc/free predeterminado de libc, por ejemplo, el tcmalloc de Google o el jemalloc de Facebook.

hidden $ g++ -O3 -std=c++11 xx.cpp /usr/lib/libtcmalloc_minimal.so.4 hidden $ ./a.out For input_size 262144: unordered-set: returns 123454321 unordered-set: took 35 milliseconds dense-hash-set: returns 123454321 dense-hash-set: took 18 milliseconds sort-and-count: returns 123454321 sort-and-count: took 34 milliseconds unordered-map: returns 123454321 unordered-map: took 36 milliseconds dense-hash-map: returns 123454321 dense-hash-map: took 13 milliseconds -------------------------- For input_size 1048576: unordered-set: returns 123454321 unordered-set: took 251 milliseconds dense-hash-set: returns 123454321 dense-hash-set: took 77 milliseconds sort-and-count: returns 123454321 sort-and-count: took 153 milliseconds unordered-map: returns 123454321 unordered-map: took 220 milliseconds dense-hash-map: returns 123454321 dense-hash-map: took 60 milliseconds -------------------------- For input_size 4194304: unordered-set: returns 123454321 unordered-set: took 1453 milliseconds dense-hash-set: returns 123454321 dense-hash-set: took 357 milliseconds sort-and-count: returns 123454321 sort-and-count: took 596 milliseconds unordered-map: returns 123454321 unordered-map: took 1461 milliseconds dense-hash-map: returns 123454321 dense-hash-map: took 296 milliseconds -------------------------- For input_size 16777216: unordered-set: returns 123454321 unordered-set: took 6664 milliseconds dense-hash-set: returns 123454321 dense-hash-set: took 1751 milliseconds sort-and-count: returns 123454321 sort-and-count: took 2513 milliseconds unordered-map: returns 123454321 unordered-map: took 7299 milliseconds dense-hash-map: returns 123454321 dense-hash-map: took 1364 milliseconds -------------------------- tcmalloc: large alloc 1073741824 bytes == 0x5f392000 @ tcmalloc: large alloc 2147483648 bytes == 0x9f392000 @ tcmalloc: large alloc 4294967296 bytes == 0x11f392000 @ For input_size 268435456: tcmalloc: large alloc 4586348544 bytes == 0x21fb92000 @ unordered-set: returns 123454321 unordered-set: took 136271 milliseconds tcmalloc: large alloc 8589934592 bytes == 0x331974000 @ tcmalloc: large alloc 2147483648 bytes == 0x21fb92000 @ dense-hash-set: returns 123454321 dense-hash-set: took 34641 milliseconds sort-and-count: returns 123454321 sort-and-count: took 47606 milliseconds tcmalloc: large alloc 2443452416 bytes == 0x21fb92000 @ unordered-map: returns 123454321 unordered-map: took 176066 milliseconds tcmalloc: large alloc 4294967296 bytes == 0x331974000 @ dense-hash-map: returns 123454321 dense-hash-map: took 26460 milliseconds --------------------------

Código:

#include <algorithm> #include <chrono> #include <cmath> #include <iostream> #include <functional> #include <string> #include <vector> #include <unordered_set> #include <unordered_map> #include <google/dense_hash_map> #include <google/dense_hash_set> using std::cout; using std::chrono::high_resolution_clock; using std::chrono::milliseconds; using std::endl; using std::string; using std::vector; using std::unordered_map; using std::unordered_set; using google::dense_hash_map; using google::dense_hash_set; class ScopedTimer { public: ScopedTimer(const string& name) : name_(name), start_time_(high_resolution_clock::now()) {} ~ScopedTimer() { cout << name_ << " took " << std::chrono::duration_cast<milliseconds>( high_resolution_clock::now() - start_time_).count() << " milliseconds" << endl; } private: const string name_; const high_resolution_clock::time_point start_time_; }; int find_using_unordered_set(const vector<int>& input_data) { unordered_set<int> numbers(input_data.size()); for(const auto& value : input_data) { auto res = numbers.insert(value); if(!res.second) { numbers.erase(res.first); } } return numbers.size() == 1 ? *numbers.begin() : -1; } int find_using_unordered_map(const vector<int>& input_data) { unordered_map<int,int> counter_map; for(const auto& value : input_data) { ++counter_map[value]; } for(const auto& map_entry : counter_map) { if(map_entry.second % 2 == 1) { return map_entry.first; } } return -1; } int find_using_dense_hash_set(const vector<int>& input_data) { dense_hash_set<int> numbers(input_data.size()); numbers.set_deleted_key(-1); numbers.set_empty_key(-2); for(const auto& value : input_data) { auto res = numbers.insert(value); if(!res.second) { numbers.erase(res.first); } } return numbers.size() == 1 ? *numbers.begin() : -1; } int find_using_dense_hash_map(const vector<int>& input_data) { dense_hash_map<int,int> counter_map; counter_map.set_deleted_key(-1); counter_map.set_empty_key(-2); for(const auto& value : input_data) { ++counter_map[value]; } for(const auto& map_entry : counter_map) { if(map_entry.second % 2 == 1) { return map_entry.first; } } return -1; } int find_using_sort_and_count(const vector<int>& input_data) { vector<int> local_copy(input_data); std::sort(local_copy.begin(), local_copy.end()); int prev_value = local_copy.front(); int counter = 0; for(const auto& value : local_copy) { if(prev_value == value) { ++counter; continue; } if(counter % 2 == 1) { return prev_value; } prev_value = value; counter = 1; } return counter == 1 ? prev_value : -1; } void execute_and_time(const string& method_name, std::function<int()> method) { ScopedTimer timer(method_name); cout << method_name << " returns " << method() << endl; } int main() { vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28}); for(const auto& input_size : input_size_vec) { // Prepare input data std::vector<int> input_data; const int magic_number = 123454321; for(int i=0;i<input_size;++i) { input_data.push_back(i); input_data.push_back(i); } input_data.push_back(magic_number); std::random_shuffle(input_data.begin(), input_data.end()); cout << "For input_size " << input_size << ":" << endl; execute_and_time("unordered-set:",std::bind(find_using_unordered_set, std::cref(input_data))); execute_and_time("dense-hash-set:",std::bind(find_using_dense_hash_set, std::cref(input_data))); execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, std::cref(input_data))); execute_and_time("unordered-map:",std::bind(find_using_unordered_map, std::cref(input_data))); execute_and_time("dense-hash-map:",std::bind(find_using_dense_hash_map, std::cref(input_data))); cout << "--------------------------" << endl; } return 0; }

Ya hay muchas respuestas excelentes, pero este es el tipo especial de pregunta que naturalmente genera muchas respuestas válidas.

Y estoy escribiendo para proporcionar una respuesta desde una perspectiva matemática (lo cual es difícil de hacer sin LaTeX), porque es importante corregir la idea falsa no abordada de que resolver el problema dado con hashes representa un problema que es "teóricamente" O(n) , pero de alguna manera "prácticamente" peor que O(n) . ¡Tal cosa sería una imposibilidad matemática!

Para aquellos que deseen profundizar en el tema, recomiendo este libro que guardé y compré como un estudiante de secundaria muy pobre, y que avivó mi interés en las matemáticas aplicadas durante muchos años por venir, esencialmente cambiando el resultado de mi vida. : http://www.amazon.com/Analysis-Algorithms-Monographs-Computer-Science/dp/0387976876

Para entender por qué el problema no es "teóricamente" O(n) , es necesario tener en cuenta que la suposición subyacente también es falsa: no es cierto que los hash sean "teóricamente" una estructura de datos O(1) .

Lo opuesto es verdad. Los hashes, en su forma pura, son solo "prácticamente" una estructura de datos O(1) , pero teóricamente todavía son una estructura de datos O(n) . (Nota: en forma híbrida, pueden lograr un rendimiento teórico de O(log n) .)

Por lo tanto, la solución sigue siendo, en el mejor de los casos, un problema O(n log n) , ya que n aproxima al infinito.

¡Puede comenzar a responder, pero todos saben que los hashes son O (1)!

Entonces, permítanme explicar cómo esa afirmación es verdadera, pero en el sentido práctico, no teórico .

Para cualquier aplicación (independientemente de n , siempre que n se conozca con anticipación -lo que llaman "fijo" en lugar de "arbitrario" en pruebas matemáticas), puede diseñar su tabla hash para que coincida con la aplicación y obtener O(1) rendimiento dentro de las limitaciones de ese entorno. Cada estructura hashing pura está diseñada para funcionar bien dentro de un rango a priori de tamaños de conjunto de datos y con la supuesta independencia de claves con respecto a la función hash.

Pero cuando dejas que n acerque al infinito, como lo exige la definición de notación Big- O , los cubos comienzan a llenarse (lo cual debe suceder según el principio de casillero) y cualquier estructura purificada pura se descompone en un algoritmo O(n) ( la notación Big- O aquí ignora el factor constante que depende de cuántos cubos hay).

Whoa! Hay mucho en esa oración.

Y entonces, en este punto, en lugar de ecuaciones, una analogía apropiada sería más útil:

Una comprensión matemática muy precisa de las tablas hash se obtiene imaginando un archivador que contiene 26 cajones, uno para cada letra del alfabeto. Cada archivo se almacena dentro del cajón que corresponde a la primera letra en el nombre del archivo.

La "función hash" es una operación O(1) , mirando la primera letra.
El almacenamiento es una operación O(1) : coloca el archivo dentro del cajón para esa letra.
Y mientras no haya más de un archivo dentro de cada cajón , la recuperación es una operación O(1) : abrir el cajón para esa letra.

Dentro de estas restricciones de diseño, esta estructura hash es O(1) .

Ahora suponga que excede las restricciones de diseño para esta estructura de hashing "archivador" y ha almacenado varios cientos de archivos. El almacenamiento ahora requiere tantas operaciones como sea necesario para encontrar un espacio vacío en cada cajón, y la recuperación requiere tantas operaciones como la cantidad de elementos dentro de cada cajón.

En comparación con tirar todos los archivos en una sola gran pila, el rendimiento promedio en general es aproximadamente mejor por un factor de 1/26 de ese tiempo. Pero recuerde, matemáticamente, uno no puede decir O(n/26) , porque la notación O(n) por definición no toma en consideración los factores constantes que afectan el rendimiento, sino solo la complejidad algorítmica como una función de n . Entonces, cuando se exceden las restricciones de diseño, la estructura de datos es O(n) .