¡Amo los algoritmos! Cada uno tiene sus propios pros y contras.
Tomemos Quicksort por ejemplo. Las personas elogian la clasificación rápida como el algoritmo de clasificación rápida, que en general es cierto. Sin embargo, para conjuntos pequeños, estoy hablando como 10–100 elementos, la ordenación por inserción es en realidad más rápida que la clasificación rápida.
Pero a pesar de todo, quicksort y strings es … ok. El problema con las cadenas es la forma en que se comparan, que es básicamente letra por letra hasta que encuentran letras diferentes. Entonces, si tiene n cadenas de tamaño s, entonces la ordenación tomará O (S * nlog (n)). Esto es genial si puede asegurarse de que cada cadena comience con letras completamente diferentes. Pero la mayoría de las veces no tendrás eso. La mayoría de las veces tendrá listas como esta: [“cama”, “cuenta”, “pan”, “plomo”, “mentido”, “dirigido”, “leer”, “líder”] donde hay una tonelada de letras comunes a la cadena. Para esto, quicksort en realidad será brutalmente lento.
- ¿Por qué el ensacado funciona tan bien para los árboles de decisión, pero no para los clasificadores lineales?
- ¿Es cierto que si me vuelvo competente en estructuras de datos y algoritmos, puedo aprender cualquier lenguaje de programación y habilidades técnicas muy rápido?
- ¿Qué libro de algoritmos introductorios debería leer una mente matemáticamente inclinada?
- ¿Cuáles son algunos algoritmos de flujo de red interesantes?
- ¿Cuáles son algunos libros que debe leer un experto en algoritmos?
Entonces, ¿cuál es la mejor manera de ordenar las cuerdas? Me gusta trie sort (que es una forma de radix sort). Básicamente, primero construyes un trie. Un trie también se conoce como árbol de prefijos. Lo que esto significa es que tiene un nodo raíz en blanco. Luego, cuando obtiene una cadena, saca la primera letra, luego verifica si existe un borde con esa letra, si atraviesa ese borde, luego llega al nodo que tiene esa letra como valor, luego obtiene el siguiente letra y repita hasta que no tenga más letras. Por ejemplo:
Una vez que se construye su trie, simplemente realiza un recorrido de preorden en orden lexicográfico creciente.
Eso es. Ese algoritmo es O (s * n + m * e) donde m es el número de nodos en el trie y e es el número de aristas. No estoy seguro de cómo crece el trie, pero mye están relacionados con syn.
Muchos algoritmos y estructuras de datos tienen muchas ventajas y desventajas que ningún algoritmo o estructura de datos puede resolver, debe elegir qué es lo mejor para su problema.
