- Ordina un array con elementi distinti LogLogN

Question

Questo non è il lavoro della mia scuola a casa. Questo è il mio lavoro a casa e sono un algoritmo di autoapprendimento.

In Algorithm Design Manual, c'è una tale accisa

4-25 Si supponga che l'array A [1..n] ha solo numeri da {1,. . . , n^2} ma che al più log log n di questi numeri appare mai. Definire un algoritmo che ordina A sostanzialmente inferiore a O (n log n).

Ho due approcci:

---

il primo approccio:

Fondamentalmente voglio fare il conteggio di ordinamento per questo problema. Posso prima eseguire la scansione dell'intero array (O (N)) e inserire tutti i numeri distinti in un array di dimensioni loglogN (int [] K).

Quindi applicare il conteggio del tipo. Tuttavia, quando si imposta la matrice di conteggio (int [] C), non è necessario impostare la sua dimensione come N^2, invece, ho impostato anche la dimensione come loglogN.

Ma in questo modo, quando contando le frequenze di ogni numero diverso, devo scansionare matrice K per ottenere indice dell'elemento (O (NloglogN) e quindi aggiornare matrice C.

---

Il secondo approccio :

Ancora, devo scandire l'intera matrice per ottenere un numero distinto matrice K con dimensioni loglogN

Poi ho solo fare una sorta di quicksort come, ma la partizione si basa sulla mediana di matrice K (. cioè, ogni volta che il pivot è un elemento della matrice K), si ripetono vamente.

Penso che questo approccio sia il migliore, con O (NlogloglogN).

---

Ho ragione? o ci sono soluzioni migliori?

accise simili esistono in Manuale Algorithm Design, come ad esempio

4-22 Dimostrare che interi n positive nel campo da 1 a k possono essere ordinati in O (n log k) tempo. Il caso interessante è quando k < < n.

4-23 Cerchiamo di ordinare una sequenza S di n interi con molte duplicazioni, in modo che il numero di interi distinti in S sia O (log n). Dare un algoritmo del tempo peggiore O (n log log n) per ordinare tali sequenze.

Ma fondamentalmente per tutte queste accise, il mio intuito pensava sempre al conteggio dell'ordinamento in quanto possiamo conoscere l'intervallo degli elementi e l'intervallo è abbastanza breve rispetto alla lunghezza dell'intero array. Ma dopo aver riflettuto più a fondo, immagino che le accise sono alla ricerca del secondo approccio, giusto?

Grazie

Answer 1

Possiamo semplicemente creare una mappa di hash che memorizza ogni elemento come chiave e la sua frequenza come valore.

Ordina questa mappa in log(n)*log(log(n)) tempo (klogk) utilizzando qualsiasi algoritmo di ordinamento.

Ora scansiona la mappa hash e aggiungi elementi al nuovo numero di frequenza dell'array di volte. In questo modo:

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

Answer 2

Counting sort è uno dei possibili modi:

1. Mostrerò questa soluzione in esempio 2, 8, 1, 5, 7, 1, 6 e tutti i numeri sono < = 3^2 = 9. Uso più elementi per rendere più chiara la mia idea.
2. Primo per ogni numero A [i] calcolare A [i]/N. Consente di chiamare questo numero first_part_of_number.
3. Ordinare questo array utilizzando il conteggio dei numeri per first_part_of_number.

4. risultati sono nella forma (esempio N = 3)

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

5. suddividerli in gruppi da first_part_of_number.

6. In questo esempio si avrà gruppi
   (0, 2) (0, 1) (0, 1)

   e

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

7. Per ciascun numero di calcolo X modulo N. consente di chiamare second_part_of_number. Aggiungere questo numero a ciascun elemento
   (0, 2, 2) (0, 1, 1) (0, 1, 1)

   e

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

8. ordine ciascun gruppo utilizzando conteggio ordina per second_part_of_number

   (0, 1, 1) (0, 1 , 1) (0, 2, 2)

   e

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

9. Ora unire tutti i gruppi e avete risultato 1, 1, 2, 6, 6, 7, 8.

Complessità: si stava utilizzando solo contando sorta su elementi < = N. Ogni elemento ha partecipato esattamente 2 "tipi" . Quindi la complessità complessiva è O (N).

Answer 3

Aggiornamento: Dopo aver scritto la risposta di seguito, @Nabb mi ha mostrato perché non era corretto. Per ulteriori informazioni, vedere Wikipedia's brief entry su Õ e i relativi collegamenti. Almeno perché è ancora necessario dare un contesto ai commenti di @ Nabb e @ Blueshift, e poiché l'intera discussione rimane interessante, la mia risposta originale viene mantenuta, come segue.

RISPOSTA ORIGINALE (errato)

Permettetemi di offrire una risposta non convenzionale: se non v'è infatti una differenza tra O (n * n) e O (n), non v'è alcuna differenza tra O (n) e O (n * log (n)).

Ora, naturalmente, sappiamo tutti che quello che ho appena detto è sbagliato, no? Dopotutto, vari autori concordano sul fatto che O (n) e O (n * log (n)) differiscono.

Tranne che non differiscono.

Una posizione così radicale che richiede naturalmente una giustificazione, quindi considera quanto segue, poi decidi.

Matematicamente, essenzialmente, l'ordine m di una funzione f (z) è tale che f (z)/(z^(m + epsilon)) converge mentre f (z)/(z^(m-epsilon)) divergenze per z di grande ampiezza e reale, positivo epsilon di grandezza arbitrariamente piccola. Il z può essere reale o complesso, anche se come abbiamo detto epsilon deve essere reale. Con questa comprensione, applica la regola di L'Hospital ad una funzione di O (n * log (n)) per vedere che non differisce in ordine da una funzione di O (n).

Sostengo che la letteratura scientifica accettata al momento è leggermente sbagliata su questo punto. Questa letteratura finirà per perfezionare la sua posizione in merito, ma non ha ancora fatto.

Ora, non mi aspetto che tu sia d'accordo con me oggi. Questa, dopotutto, è semplicemente una risposta su Stackoverflow - e che cosa è comparato a un libro di computer-science pubblicato, formalmente revisionato da un peer-review - per non parlare di un riparo di questi libri? Non dovresti essere d'accordo con me oggi, prendi solo quello che ho scritto sotto consiglio, rimugina sulla tua mente nelle prossime settimane, consulta uno o due dei libri di informatica di cui sopra che prendono l'altra posizione e prendi la tua stessa decisione .

Incidentalmente, un'implicazione controtendente della posizione di questa risposta è che si può accedere a un albero binario bilanciato in O (1). Di nuovo, sappiamo tutti che è falso, giusto? Dovrebbe essere O (log (n)). Ma ricorda: la notazione O() non è mai stata pensata per dare una misura precisa delle richieste computazionali. A meno che lo n sia molto grande, altri fattori possono essere più importanti dell'ordine di una funzione. Ma, anche per n = 1 milione, log (n) è solo 20, confrontato, diciamo, con sqrt (n), che è 1000. E potrei andare avanti in questo modo.

In ogni caso, pensaci. Anche se, alla fine, decidi di non essere d'accordo con me, potresti comunque trovare la posizione interessante. Da parte mia, non sono sicuro di quanto sia utile la notazione O() quando si tratta di O (registra qualcosa).

@Blueshift pone alcune domande interessanti e solleva alcuni punti validi nei commenti seguenti.Ti raccomando di leggere le sue parole. Non ho molto da aggiungere a ciò che ha da dire, se non osservarlo, perché pochi programmatori hanno (o hanno bisogno) una solida base nella teoria matematica della variabile complessa, la O (log (n)) la notazione ha ingannato probabilmente, letteralmente centinaia di migliaia di programmatori, per credere che stavano ottenendo guadagni per lo più illusori nell'efficienza computazionale. Raramente, in pratica, la riduzione di O (n * log (n)) a O (n) ti fa davvero guadagnare quello che potresti pensare che ti compra, a meno che tu non abbia una chiara immagine mentale di quanto sia incredibilmente lenta una funzione del logaritmo - mentre ridurre O (n) anche a O (sqrt (n)) può comprarti molto. Un matematico avrebbe detto al computer scienziato decenni fa, ma lo scienziato informatico non stava ascoltando, aveva fretta o non capiva il punto. E va tutto bene. Non mi dispiace. Ci sono molti punti su altri argomenti che non capisco, anche quando i punti mi vengono accuratamente spiegati. Ma questo è un punto in cui credo di capire. Fondamentalmente, è un punto matematico, non un punto computer, ed è un punto sul quale mi trovo a schierarmi con Lebedev e i matematici piuttosto che con Knuth e gli informatici. Questo è tutto.

Answer 4

ho intenzione di tradire la mia conoscenza limitata della complessità algoritmica qui, ma:

non avrebbe senso per eseguire la scansione l'array una volta e costruire qualcosa di simile a un albero di auto-bilanciamento? Come sappiamo, il numero di nodi nell'albero aumenterà (log log n) è relativamente economico (?) Per trovare un numero ogni volta. Se viene trovato un numero di ripetizione (probabile), un contatore in quel nodo viene incrementato. Quindi per costruire l'array ordinato, leggi l'albero in ordine.

Forse qualcuno può commentare la complessità di questo e di eventuali difetti.