Quale sarà la peggiore complessità per l'ordinamento delle stringhe n con caratteri n ciascuno? Sarà solo n volte la sua media. case O(n log n) o qualcos'altro ...?Ordinamento di stringhe utilizzando Fusione Ordina
Come @orangeoctopus, l'utilizzo dell'algoritmo di classificazione standard su un insieme di stringhe n di dimensioni n comporterà il calcolo O(n^2 * logn).
Tuttavia, si noti che è possibile effettuare il in O(n^2), con variazioni su radix sort.
Il modo più semplice per farlo [a mio parere] - è
O(n) e lo fate n volte - totale di O(n^2)E 'facile vedere, non si può fare di meglio allora O(n^2), dal momento che solo la lettura dei dati è O(n^2), quindi questa soluzione è ottimale in termini di notazione O-grande di tempo complessità.
Penso invece di dire "DFS", dicendo "pre-order traversal" sarebbe più chiaro. – CEGRD
È possibile ottenere 'O (n^2) 'senza usare anche trie? – Kshitij
@Kshitij Sì, fai un ordinamento di tipo radix sulla stringa, il trie è solo un suggerimento - un ordinamento standard di radix funzionerà qui - usando i caratteri (o la loro rappresentazione bit) ogni iterazione per raggiungere l'attuale ordine parziale, fino a esaurire tutti i bit /personaggi. Ciò richiederà anche 'O (n^2)'. – amit
Quando si parla della notazione O con due cose con diverse lunghezze, in genere si desidera utilizzare variabili diverse, ad esempio M e N.
Quindi, se il merge sort è O(N log N), dove N è il numero di stringhe ... e il confronto di due stringhe è O(M) dove M scale con la lunghezza della stringa, allora sarete lasciati con:
O(N log N) * O(M)
o
O(M N log N)
dove M è la lunghezza della stringa e N è il numero di stringhe. Vuoi usare etichette diverse perché non significano la stessa cosa.
Nel strano caso in cui la durata media della stringa scale con il numero di stringhe, come se si avesse una matrice memorizzata in stringhe o qualcosa del genere, si potrebbe sostenere che M = N, e poi si sarebbe avere O(N^2 log N)
Non intendete "O (M) dove M ..." invece di "O (N) dove N ..."? E mentre ciò è il peggiore delle prestazioni, come richiesto, va notato che le prestazioni nel caso medio per il confronto di due stringhe sono O (1) poiché diventa sempre meno probabile che sia necessario visitare ogni carattere aggiuntivo nelle stringhe. – xan
Certo, intendevo che erano separati, ma l'ho cambiato per usare 'M' per essere più chiaro. Sta chiedendo "la peggiore complessità", ma dando una dimensione "media" della puntura ... quindi è ancora O (N), giusto? –
Sì, la domanda è un po 'oscura con il suo mix di peggiore e media. Penso che la tua risposta sarebbe più forte per coprire entrambi. – xan
L'ordinamento di n elementi con MergeSort richiede il confronto O(N LogN). Se il tempo di confrontare due articoli è O(1), il tempo totale di esecuzione sarà O(N logN). Tuttavia, il confronto di due stringhe di lunghezza N richiede tempo O(N), quindi un'implementazione ingenua potrebbe rimanere bloccata con il tempo O(N*N logN).
Questo sembra uno spreco perché non stiamo sfruttando il fatto che ci sono solo le stringhe N in giro per fare confronti. Potremmo in qualche modo preelaborare le stringhe in modo che i confronti richiedano meno tempo in media.
Ecco un'idea. Crea una struttura Trie e metti lì le stringhe. Il trie avrà nodi O(N*N) e richiederà il tempo di costruzione O(N*N). Attraversa l'albero e metti un intero "classifica" per ogni nodo all'albero; Se R (N1) < R (N2), la stringa associata a Nodo1 viene prima della stringa associata a Nodo2 in un dizionario.
Ora procedere con Mergesort, effettuare i confronti nel tempo O(1) guardando il Trie. Il tempo di esecuzione totale sarà O(N*N + N*logN) = O(N*N)
Modifica: La mia risposta è molto simile a quella di @amit. Comunque procedo con il mergesort dove procede con radixsort dopo la fase di costruzione del trie.
Mantenete anche le parole di mappatura dell'indice sui nodi trie in modo da poter accedere a tali classifiche durante l'ordinamento di fusione? chiarimento per favore. Inoltre, penso che dovresti includere anche il costo del viaggio. Quindi la complessità dovrebbe essere O (N * N + N * N + N * logN). Se questo è vero, allora l'approccio di ordinamento radix sembra migliore poiché è O (N * N + N * N). – CEGRD
@CERGD: la notazione Big O riguarda solo la crescita asintotica rispetto alla dimensione dell'input; non si occupa di fattori costanti, O (2 * N * N + NlogN) = O (N * N). Rivisitando la domanda dopo alcuni mesi, è chiaro che la risposta di amit è più semplice e veloce. Tuttavia, non sono d'accordo con la tua argomentazione: l'unico modo per misurare la performance effettiva è usare un cronometro, non guardare i fattori costanti nella notazione O. Ci sono persino casi in cui un algoritmo con una funzione O() più grande batte l'altro in situazioni pratiche. –
Di cosa stai parlando qui? – uday
Non è chiaro cosa stai chiedendo. –
modificato la mia domanda ..... – Abhishek