algorithm - tipos - rango de una matriz

Algoritmo-Ordena una matriz con elementos distintos de LogLogN (4)

La clasificación de conteo es una de las posibles maneras:

Demostraré esta solución en los ejemplos 2, 8, 1, 5, 7, 1, 6 y todos los números son <= 3 ^ 2 = 9. Utilizo más elementos para hacer que mi idea sea más clara.
Primero para cada número A [i] calcule A [i] / N. Permite llamar a este número first_part_of_number .
Ordene esta matriz usando el conteo first_part_of_number por first_part_of_number .
Los resultados están en forma (ejemplo para N = 3)
(0, 2)
(0, 1)
(0, 1)
(2, 8)
(2, 6)
(2, 7)
(2, 6)
first_part_of_number en grupos por first_part_of_number .
En este ejemplo, tendrás grupos
(0, 2) (0, 1) (0, 1)
y
(2, 8) (2, 6) (2, 7) (2, 6)
Para cada número, calcule X módulo N. second_part_of_number . Agregue este número a cada elemento
(0, 2, 2) (0, 1, 1) (0, 1, 1)
y
(2, 8, 2) (2, 6, 0) (2, 7, 1) (2, 6, 0)
Ordene cada grupo usando el tipo de conteo por second_part_of_number
(0, 1, 1) (0, 1, 1) (0, 2, 2)
y
(2, 6, 0) (2, 6, 0) (2, 7, 1) (2, 8, 2)
Ahora combine todos los grupos y obtendrá los resultados 1, 1, 2, 6, 6, 7, 8.

Complejidad: Usted estaba usando solo contar elementos de clasificación <= N. Cada elemento participó en exactamente 2 "géneros". Entonces, la complejidad general es O (N).

Este no es el trabajo de mi casa en la escuela. Este es mi propio trabajo a domicilio y soy algoritmo de autoaprendizaje.

En Algorithm Design Manual , existe tal impuesto especial

4-25 Suponga que la matriz A [1..n] solo tiene números de {1,. . . , n ^ 2} pero que como mucho log log n de estos números aparece alguna vez. Diseñe un algoritmo que clasifique A en sustancialmente menos que O (n log n).

Tengo dos enfoques:

El primer acercamiento:

Básicamente quiero hacer un conteo para este problema. Primero puedo escanear toda la matriz (O (N)) y poner todos los números distintos en una matriz de tamaño loglogN (int [] K).

Luego aplica el conteo de clasificación. Sin embargo, cuando configuro la matriz de conteo (int [] C), no necesito establecer su tamaño como N ^ 2, en su lugar, configuré el tamaño como loglogN también.

Pero de esta manera, al contar las frecuencias de cada número distinto, tengo que escanear la matriz K para obtener el índice de ese elemento (O (NloglogN) y luego actualizar la matriz C.

El segundo enfoque:

Una vez más, tengo que escanear todo el conjunto para obtener un conjunto de números distintos K con tamaño loglogN.

Luego hago una especie de quicksort, pero la partición se basa en la mediana de la matriz K (es decir, cada vez que el pivote es un elemento de la matriz K), recursivamente.

Creo que este enfoque será el mejor, con O (NlogloglogN).

¿Estoy en lo cierto? o hay mejores soluciones?

Exises similares existen en Algorithm Design Manual, como

4-22 Muestre que n enteros positivos en el rango de 1 a k se pueden ordenar en el tiempo O (n log k). El caso interesante es cuando k << n.
4-23 Buscamos ordenar una secuencia S de n enteros con muchas duplicaciones, de modo que el número de enteros distintos en S sea O (log n). Proporcione un algoritmo de tiempo del caso más desfavorable O (n log log n) para ordenar tales secuencias.

Pero básicamente, para todos estos impuestos especiales, mi intuitivo siempre estaba pensando en contar, ya que podemos conocer el rango de los elementos y el rango es lo suficientemente corto en comparación con la longitud de toda la matriz. Pero después de pensar más profundamente, supongo que lo que están buscando los impuestos especiales es el segundo enfoque, ¿verdad?

Gracias

Voy a traicionar mi conocimiento limitado de la complejidad algorítmica aquí, pero:

¿No tendría sentido escanear la matriz una vez y construir algo así como un árbol de auto-equilibrio? Como sabemos, la cantidad de nodos en el árbol solo crecerá (log log n), es relativamente barato (?) Encontrar un número cada vez. Si se encuentra un número de repetición (probable), se incrementa un contador en ese nodo. Luego, para construir la matriz ordenada, lea el árbol en orden.

Tal vez alguien pueda comentar sobre la complejidad de este y cualquier defecto.

Actualización: Después de escribir la respuesta a continuación, @Nabb me mostró por qué era incorrecta. Para obtener más información, consulte la breve entrada de Wikipedia en Õ, y los enlaces de allí. Al menos porque todavía es necesario dar contexto a los comentarios de @ Nabb y @ Blueshift, y como toda la discusión sigue siendo interesante, mi respuesta original se conserva de la siguiente manera.

RESPUESTA ORIGINAL (INCORRECTA)

Permítanme ofrecer una respuesta no convencional: aunque hay una diferencia entre O (n * n) y O (n), no hay diferencia entre O (n) y O (n * log (n)).

Ahora, por supuesto, todos sabemos que lo que acabo de decir es incorrecto, ¿verdad? Después de todo, varios autores coinciden en que O (n) y O (n * log (n)) difieren.

Excepto que no son diferentes.

Por lo tanto, una posición de apariencia radical exige naturalmente una justificación, así que considere lo siguiente, luego tome su propia decisión.

Matemáticamente, esencialmente, el orden m de una función f (z) es tal que f (z) / (z ^ (m + epsilon)) converge mientras que f (z) / (z ^ (m-epsilon)) diverge para z de gran magnitud y épsilon positivo real de magnitud arbitrariamente pequeña. La z puede ser real o compleja, aunque como dijimos épsilon debe ser real. Con este entendimiento, aplique la regla de L''Hospital a una función de O (n * log (n)) para ver que no difiera en orden de una función de O (n).

Yo sostendría que la literatura de ciencias de la computación aceptada en la actualidad está ligeramente equivocada en este punto. Esta literatura finalmente refinará su posición en el asunto, pero aún no lo ha hecho.

Ahora, no espero que estés de acuerdo conmigo hoy. Después de todo, esto no es más que una respuesta en , y ¿qué es eso en comparación con un libro de ciencias de la computación editado, formalmente revisado por pares, sin mencionar un montón de esos libros? No deberías estar de acuerdo conmigo hoy, solo toma lo que he escrito por recomendación, reflexiona sobre esto en las próximas semanas, consulta uno o dos de los libros de ciencias de la computación antes mencionados que toman la otra posición, y toma una decisión .

Incidentalmente, una implicación contra intuitiva de la posición de esta respuesta es que uno puede acceder a un árbol binario equilibrado en O (1) tiempo. Una vez más, todos sabemos que eso es falso, ¿verdad? Se supone que es O (log (n)). Pero recuerde: la notación O () nunca tuvo la intención de dar una medida precisa de las demandas computacionales. A menos que n sea muy grande, otros factores pueden ser más importantes que el orden de una función. Pero, incluso para n = 1 millón, log (n) es solo 20, comparado, por ejemplo, con sqrt (n), que es 1000. Y podría seguir en este sentido.

De todos modos, piense un poco. Incluso si, finalmente, decides que no estás de acuerdo conmigo, es posible que encuentres interesante la posición. Por mi parte, no estoy seguro de cuán útil es la notación O () cuando se trata de O (registrar algo).

@Blueshift hace algunas preguntas interesantes y plantea algunos puntos válidos en los comentarios a continuación. Te recomiendo que leas sus palabras. Realmente no tengo mucho que agregar a lo que tiene que decir, excepto observar que, debido a que pocos programadores tienen (o necesitan) una sólida base en la teoría matemática de la variable compleja, el O (log (n)) la notación ha confundido probablemente, literalmente, a cientos de miles de programadores para creer que estaban logrando ganancias principalmente ilusorias en eficiencia computacional. Raramente, en la práctica, reducir O (n * log (n)) a O (n) realmente te compra lo que crees que te compra, a menos que tengas una imagen mental clara de la increíblemente lenta función que realmente es el logaritmo: mientras que reducir O (n) hasta O (sqrt (n)) puede comprarle mucho. Un matemático le habría dicho al informático hace décadas, pero el informático no estaba escuchando, tenía prisa o no entendía el punto. Y eso está bien. No me importa Hay muchos puntos sobre otros temas que no entiendo, incluso cuando los puntos me son explicados cuidadosamente. Pero este es un punto que creo que sí entiendo. Fundamentalmente, es un punto matemático, no un punto informático, y es un punto en el que me pongo del lado de Lebedev y los matemáticos en lugar de hacerlo con Knuth y los informáticos. Esto es todo.

Solo podemos crear un mapa hash que almacene cada elemento como clave y su frecuencia como valor.

Ordene este mapa en log(n)*log(log(n)) time ie (klogk) usando cualquier algoritmo de clasificación.

Ahora escanee el mapa hash y agregue elementos a la nueva frecuencia de serie número de veces. Al igual que:

total time = 2n+log(n)*log(log(n)) = O(n)