Puede encontrar la complejidad de tiempo O (n) para ordenar una matriz de dígitos en el mejor caso de ordenación por inserción ( eficiente para conjuntos de datos que ya están sustancialmente ordenados: la complejidad de tiempo es O (nk) cuando cada elemento en la entrada no es más que k se aleja de su posición ordenada ).
Pero, en general, tenemos a lo sumo la complejidad del tiempo O (nlogn) para la clasificación de algoritmos como la combinación de clasificación, clasificación de montón, clasificación rápida (el mejor de los casos).
Ok, si insistes más, entonces puedo llevarte a Conteo de clasificación – GeeksforGeeks, pero necesita espacio adicional. La clasificación de conteo es una técnica de clasificación basada en teclas entre un rango específico. Funciona contando el número de objetos que tienen valores clave distintos (tipo de hash). Luego haciendo algo de aritmética para calcular la posición de cada objeto en la secuencia de salida.
- ¿Cómo determina el algoritmo de alimentación de Quora el contenido a mostrar?
- ¿Cómo describirías el algoritmo de Quora usando una ecuación?
- ¿Cuál es la operación que tiene la constante más pequeña?
- Con la complejidad de O (n) u O (1) u O (log n), ¿cómo encuentro cuándo se romperá una bola rompible cuando se lance desde un piso de un edificio que tiene más de 100 pisos?
- ¿Puede un camino más corto contener un ciclo?
Vamos a entenderlo con la ayuda de un ejemplo.
Para simplificar, considere los datos en el rango de 0 a 9. Datos de entrada: 1, 4, 1, 2, 7, 5, 2 1) Tome una matriz de conteo para almacenar el conteo de cada objeto único. Índice: 0 1 2 3 4 5 6 7 8 9 Recuento: 0 2 2 0 1 1 0 1 0 0 2) Modifique la matriz de conteo de modo que cada elemento en cada índice almacena la suma de los recuentos anteriores. Índice: 0 1 2 3 4 5 6 7 8 9 Cuenta: 0 2 4 4 5 6 6 7 7 7 La matriz de recuento modificada indica la posición de cada objeto en La secuencia de salida. 3) Salida de cada objeto de la secuencia de entrada seguido de disminuyendo su recuento en 1. Procese los datos de entrada: 1, 4, 1, 2, 7, 5, 2. La posición de 1 es 2. Ponga los datos 1 en el índice 2 en la salida. Disminuya el recuento en 1 para colocar siguiente dato 1 en un índice 1 más pequeño que este índice.
Complejidad de tiempo: O (n + k) donde n es el número de elementos en la matriz de entrada yk es el rango de entrada.
Espacio auxiliar: O (n + k)
Salud !!!!
