Clasificación de cadenas usando Combinar Ordenar

Question

¿Cuál será la peor complejidad para ordenar cadenas de n que tengan n caracteres cada una? ¿Será solo n veces su promedio? caso O(n log n) o algo más ...?

Answer 1

Como @orangeoctopus, utilizando el algoritmo de clasificación estándar en una colección de n cadenas de tamaño n dará como resultado O(n^2 * logn) cálculo.

Sin embargo - Tenga en cuenta que puede hacerlo en O(n^2), con variaciones en radix sort.

La forma más sencilla de hacerlo [en mi opinión] - es

1. construir un trie, y rellenarla con todas sus cadenas. Entrando cada cadena es O(n) y lo haces n veces - total de O(n^2)
2. hacer un DFS en el trie, cada vez que se encuentra con la marca de final de cadena - añadirlo a la colección ordenada. El orden de las cadenas añadidas de esta manera es lexicográficamente, por lo que su lista se ordenará lexicográficamente cuando haya terminado.

Es fácil ver que no se puede hacer nada mejor que O(n^2), ya que sólo la lectura de los datos es O(n^2), por tanto, esta solución es óptima en términos de gran O notación de la complejidad del tiempo.

Answer 2

Cuando habla de la notación O con dos elementos con diferentes longitudes, normalmente desea utilizar variables diferentes, como M y N.

lo tanto, si la combinación de una especie es O(N log N), donde N es el número de cadenas ... y la comparación de dos cadenas es O(M) donde M escalas con la longitud de la cadena, y se le dejó con:

O(N log N) * O(M) 

o

O(M N log N) 

donde M es la longitud de la cadena y N es el número de cadenas. Desea utilizar etiquetas diferentes porque no significan lo mismo.

En el extraño caso en el que la longitud media de cadena de escala con el número de cadenas, como si tuviera una matriz almacenada en cadenas o algo por el estilo, se podría argumentar que M = N, y entonces tendría O(N^2 log N)

Answer 3

Ordenar n elementos con MergeSort requiere O(N LogN) comparaciones. Si el tiempo para comparar dos elementos es O(1), el tiempo total de ejecución será O(N logN). Sin embargo, la comparación de dos cadenas de longitud N requiere O(N) de tiempo, por lo que una implementación ingenua podría quedarse atascada con el tiempo O(N*N logN).

Esto parece un desperdicio porque no estamos aprovechando el hecho de que solo hay N cadenas para hacer comparaciones. De alguna manera, podemos preprocesar las cadenas para que las comparaciones tomen menos tiempo en promedio.

Aquí hay una idea. Crea una estructura Trie y pon N cadenas allí. El trie tendrá O(N*N) nodos y requerirá O(N*N) tiempo para compilar. Atraviese el árbol y coloque un "ranking" entero a cada nodo en el árbol; Si R (N1) < R (N2), la cadena asociada con el Nodo1 aparece antes que la cadena asociada con el Nodo2 en un diccionario.

Ahora proceda con Mergesort, haga las comparaciones en tiempo O(1) mirando el Trie. El tiempo total de ejecución será O(N*N + N*logN) = O(N*N)

Editar: Mi respuesta es muy similar a la de @amit. Sin embargo procedo con mergesort donde procede con radixsort después del paso de construcción trie.