algorithm - subestimar - ¿Cuál es el algoritmo más subestimado o poco conocido pero útil?
subestimar frases (3)
El árbol trie / ternario ... ¡El prefijo rápido coincide! Ciertamente los he usado más que montones o estructuras de listas vinculadas explícitas (aunque las listas vinculadas implícitas con "siguientes" a menudo son útiles).
Estoy buscando un algoritmo o estructura de datos que sea tan desconocido como útil que pienses que es un descuido horrible por parte de la informática o la comunidad de programación. Si todos pudiéramos aprender esto, se haría mucho bien en muchos programas futuros.
El mejor que puedo encontrar es la búsqueda de interpolación, que solo muy pocos programadores saben, mientras que todos conocen la búsqueda binaria. Creo que hay pocas dudas de que buscar una lista ordenada rápidamente es un algoritmo bastante útil y fundamental.
Los dos son casi idénticos de implementar, por lo que no es un problema.
Realiza O (log (log (n))) en datos distribuidos uniformemente, en comparación con búsquedas binarias O (log (n)). Eso significa que buscar 4 billones de números requiere solo 5 sondas contra 32, ¡eso es MUCHO mejor!
En datos no perfectamente uniformes, todavía funciona muy bien la mayor parte del tiempo. Solo cuando los datos están realmente sesgados es tan malo como la búsqueda binaria o peor. Es O (n) el peor de los casos cuando los datos están muy sesgados, pero esto no es muy común en la mayoría de las situaciones del mundo real.
Aún así, uno puede construir un algoritmo par / impar para alternar entre los dos y obtener el peor caso de búsqueda binaria con el caso promedio de búsqueda de interpolación para mitigar las situaciones extremas.
Realmente no hay una buena razón para que la mayoría de los programadores / bibliotecas lo pasen por alto.
¿Alguien más puede vencer eso?
Nomino a smoothsort En el lugar, complejidad de tiempo O (n log n) peor caso / O (n) mejor caso.
Otra nominación para smoothsort. En teoría, es bastante hermoso y es asintóticamente tan bueno como puede ser.
En caso de que tenga curiosidad, escribí una explanation de cómo funciona el orden y de dónde viene en mi sitio personal.
Además, estoy totalmente de acuerdo en que la búsqueda de interpolación es realmente impresionante. Me alegra que alguien más haya oído hablar de esto. :-)