Así que aquí está la pregunta:otro algoritmo de empleo-Entrevista
Supongamos que tiene 100 mil números enteros que varía de 1 a 1 millón. Por favor, clasifique los enteros. La complejidad del tiempo debe ser O (n).
Cualquiera que comparta sus ideas es muy apreciado.
Suena como un tipo de conteo directo.
El espacio es constante. El tiempo de ejecución es O (n).
Gotcha, gracias, parece que esta pregunta no es tan difícil. Simplemente odio yo mismo – Tracy
el tiempo de ejecución también es constante, a menos que cambie el pregunta, que como te escribí debería. Entonces Space es O (n), el tiempo de ejecución es O (n). No puedes tenerlo de las dos maneras. – piccolbo
Una cosa más para agregar a esta buena respuesta.Para la configuración 4, debe recorrer la matriz hacia atrás si desea tener un orden estable (es decir, en el caso de las relaciones, las cosas se imprimen en el orden de la matriz preordenada). –
Usar clasificación de recuento. Simplemente cuente todos ellos (O (n)), y luego cree llenar la matriz de resultados (O (n), nuevamente).
La sugerencia debe ser que van de 1 a 1 millón.
Ver pigeonhole sort
Tienes que utilizar cualquier algoritmo de clasificación conocidos con la complejidad O (n)
Dado que el problema ha fijado tamaño e incluye un conjunto finito de los casos, cualquier algoritmo de ordenación terminará en O (1). Debe decirle al probador que regrese a la escuela de análisis de algoritmos. Una forma posible de generalizar este problema a un conjunto infinito es: tiene una matriz de tamaño n con números que varían en [0, 10n]. ¿Puedes ordenarlo en O (n)? Eso tiene sentido para mí. O podrías parametrizar el problema con el tamaño de la matriz y el rango de los enteros y obtener un límite de O (f (n, k)). El problema es cuando recibes una pregunta como esta en una entrevista, ¿qué haces? ¿Tratas de adivinar qué le gustaría escuchar al entrevistador o dices algo como "déjame reformular tu pregunta"? ¿O simplemente te desplazas hacia la salida con una gran sonrisa?
Clasificación de conteo: http://en.wikipedia.org/wiki/Counting_sort –
@Paul R: El artículo de Wikipedia dice que es O (n + k), y solo es eficiente si n> k. En este caso n = 100,000 yk = 1,000,000. –
Or radix sort (1 millón es 20 bits, por lo que 20 pasa más de 100.000 enteros en el caso ingenuo; el recuento ingenuo requiere que ponga a cero el millón de contadores (no usar una tabla hash, pero no clave los resultados en orden) , por lo que debe ordenarlo, utilizando un mapa de árbol no, pero la inserción de tiempo no constante) y luego iterar sobre ellos para obtener el resultado, que también es del orden de 2 millones de operaciones; clasificación de raíz binaria puede ser hecho en su lugar por lo que no requiere almacenamiento adicional. –