- Ordene una matriz con elementos distintos de LogLogN

Question

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

En Algorithm Design Manual, existe una especial tal

4-25 Suponga que la matriz A [1..n] solamente 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 enfoque:

Básicamente quiero hacer recuento de clasificación 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 aplique el tipo de conteo. 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, I tiene que escanear matriz K para obtener el índice de ese elemento (O (NloglogN) y luego actualizar matriz C.

---

El segundo enfoque :

una vez más, tengo que escanear toda la matriz para obtener una matriz número distinto K con el tamaño loglogN

Entonces acabo de hacer una especie de clasificación rápida como, 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), recurre sively

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

---

Am I right? o hay mejores soluciones? Existen

impuestos especiales similares en el Manual de diseño de algoritmos, tales como

4-22 Mostrar que los enteros positivos n en el rango de 1 a k se pueden clasificar en O (n log k) tiempo. 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

Answer 1

Podemos simplemente crear un mapa hash que almacene cada elemento como clave y su frecuencia como valor.

Ordenar este mapa en log(n)*log(log(n)) tiempo i.e (klogk) utilizando cualquier algoritmo de clasificación.

Ahora escanee el mapa hash y agregue elementos al nuevo número de frecuencia de la serie de veces. De este modo:

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

Answer 2

Contando tipo es una de las posibles formas:

1. voy a demostrar esta solución en el ejemplo 2, 8, 1, 5, 7, 1, 6 y todo número son < = 3^2 = 9. Uso más elementos para hacer que mi idea sea más clara.
2. Primero para cada número A [i] calcule A [i]/N. Llame a este número first_part_of_number.
3. Ordene esta matriz usando la clasificación de conteo por first_part_of_number.

4. resultados están en la forma (ejemplo para N = 3)

   (0, 2)
   (0, 1)
   (0, 1)
   (2, 8)
   (2, 6)
   (2, 7)
   (2, 6)

5. dividirlos en grupos por first_part_of_number.

6. En este ejemplo tendrá grupos
   (0, 2) (0, 1) (0, 1)

   y

   (2, 8) (2, 6) (2, 7) (2, 6)

7. Para cada número de cómputo X modulo N. Lets llaman second_part_of_number. Añadir 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)

8. Ordenar cada grupo usando conteo ordenar 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)

9. Ahora combinar todos los grupos y tiene resultado 1, 1, 2, 6, 6, 7, 8.

Complejidad: estaba utilizando solamente contando tipo de elementos < = N. Cada elemento participó en exactamente 2 "tipo" . Entonces, la complejidad general es O (N).

Answer 3

Actualización: Después de escribir a continuación la respuesta, @Nabb me mostró por qué era incorrecta. Para obtener más información, consulte Wikipedia's brief entry en Õ, y los enlaces desde 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 (incorrecto)

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

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

Excepto que no son diferentes.

tan radical de apariencia natural exige una posición de justificación, por lo que considerar lo siguiente, a continuación, hacer su propia decisión.

Matemáticamente, esencialmente, el orden m de una función f (z) es tal que f (z)/(z^(+ epsilon m)) converge mientras f (z)/(z^(m-épsilon)) diverge para z de gran magnitud y real, positivo epsilon de magnitud arbitrariamente pequeña. El z puede ser real o complejo, 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 informática aceptado en la actualidad es ligeramente errónea en este punto. Esta literatura finalmente refinará su posición en el asunto, pero aún no lo ha hecho.

Ahora, no espero que usted esté de acuerdo conmigo hoy. Después de todo, esto no es más que una respuesta en Stackoverflow, 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 tu propia decisión .

Por cierto, una implicación contrario a la intuición de la posición de esta respuesta es que se 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, piensa en ello. 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.

Answer 4

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

no tendría sentido para escanear la matriz de una vez y construir algo 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.

Quizás alguien pueda comentar sobre la complejidad de este y cualquier error.