Algoritmi: come riassumo O (n) e O (nlog (n)) insieme?

Naviga le tue risposte
21

Ho il seguente algoritmo che trova i duplicati e li rimuove: 

public static int numDuplicatesB(int[] arr) {
    Sort.mergesort(arr);
    int numDups = 0;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] == arr[i - 1]) {
            numDups++;
} }
    return numDups;
}

Sto cercando di trovare la peggiore complessità temporale di questo. So che mergesort è nlog(n) , e nel mio ciclo for I iterating su tutto il set di dati in modo che possa contare come n . Non sono sicuro di cosa fare con questi numeri però. Dovrei solo sommarli insieme? Se dovessi farlo, come lo farei?

    
posta chopper draw lion4 08.10.2014 - 22:59
fonte

5 risposte

65
O(n) + O(n log(n)) = O(n log(n))

Per complessità Big O, tutto ciò che ti interessa è il termine dominante. n log(n) domina n quindi questo è l'unico termine che ti interessa.

    
risposta data 08.10.2014 - 23:16
fonte
56

Facciamo un ragionamento e ricordiamo la definizione di O . Quello che userò è per il limite all'infinito.

Hai ragione affermando che esegui due operazioni con i corrispondenti limiti asintotici di O(n) e O(nlog(n)) ma combinarle in un singolo limite non è semplice come aggiungere le due funzioni. Sai che la tua funzione richiede almeno O(n) di tempo e almeno O(nlog(n)) di tempo. Quindi la classe di complessità per la tua funzione è l'unione di O(n) e O(nlog(n)) ma O(nlog(n)) è un superset di O(n) quindi in realtà è solo O(nlog(n)) .

    
risposta data 08.10.2014 - 23:47
fonte
5

Se avessi intenzione di impostarlo a mano lunga sarebbe più o meno così:

Supponiamo che il tempo totale sia: a n + b n log (n), dove a e b sono costanti (ignorando i termini dell'ordine inferiore).

Come n va all'infinito (a n + b n log (n)) / n log (n) - > a / log (n) + b - > b

Quindi il tempo totale è O (b n log (n)) = O (n log (n)).

    
risposta data 09.10.2014 - 09:42
fonte
2

Inizia con la definizione di O ():

O (n log n) significa "meno di C n log n, se n è grande".

O (n) significa "meno di D n, se n è grande".

Se si aggiungono entrambi, il risultato è inferiore a C n log n + D n < C n log n + D n log n < (C + D) n log n = O (n log n).

In generale, se f (n) > C g (n) per grande n e alcuni C > 0, quindi O (f (n)) + O (g (n)) = O (f (n)). E dopo aver fatto alcuni casi usando la definizione di O (), saprai cosa puoi e cosa non puoi fare.

    
risposta data 09.10.2014 - 16:40
fonte
1

La notazione O grande è definita come un set:

Quindi contiene tutte le funzioni che sono - a partire da un punto arbitrario di grandi dimensioni - sempre più piccolo di g.

Ora, quando hai una funzione in epoineeseguiun'altracheaumentapiùlentamentedig,ècertamentepiùlentadi2g.Quindieseguirequalcosadipiùlentodignoncambieràlaclassedicomplessità.

Piùformalmente:

Puoi facilmente provarlo.

TL; DR

È ancora

    
risposta data 13.10.2014 - 22:02
fonte

Leggi altre domande sui tag

Perché XML non è chiamato EML? Preferisci la concisione o la leggibilità nel tuo codice? [chiuso]