Algoritmo di analisi Domanda

StackOverflow https://stackoverflow.com/questions/1066660

  •  21-08-2019
  •  | 
  •  

Domanda

. NOTA: Sono ultra-newbie sull'analisi algoritmo in modo da non prendere nessuna delle mie affermazioni come verità assolute, qualsiasi cosa (o tutto) che Premetto potrebbe essere sbagliato

Ciao, sto leggendo di analisi algoritmo e "Big-O-notazione" e mi sono perplesso su qualcosa.

Si supponga che vi viene chiesto di stampare tutte le permutazioni di un array di caratteri, per [a, b, c] che sarebbe ab, ac, ba, BC, CA e CB.

Beh un modo per farlo sarebbe (in Java): 

for(int i = 0; i < arr.length; i++)
    for(int q = 0; q < arr.length; q++)
        if(i != q)
            System.out.println(arr[i] + " " + arr[q]);

Questo algoritmo ha una notazione di O (n 2 ) se sono corrette.

ho pensato altro modo di farlo: 

for(int i = 0; i < arr.length; i++)
    for(int q = i+1; q < arr.length; q++)
    {
        System.out.println(arr[i] + " " + arr[q]);
        System.out.println(arr[q] + " " + arr[i]);
    }

Ora questo algoritmo è due volte più veloce rispetto all'originale , ma se non mi sbaglio, per il grande-notazione O è anche un O ( 2 )

È corretto? Probabilmente non è così sarò riformulare: Dove mi sbaglio ??

È stato utile?

Soluzione

Hai ragione. Notazione O vi dà un'idea di come le scale algoritmo, non la velocità assoluta. Se si aggiungono più possibilità, entrambe le soluzioni scalerà allo stesso modo, ma saranno sempre due volte più veloce l'altro.

O (n) operazioni possono essere anche più lento di O (n ^ 2) operazioni, per sufficientemente piccolo 'n'. Immaginate il vostro O (n) di calcolo consiste nel prelievo di 5 radici quadrate, e il vostro O (n ^ 2) soluzione è un singolo confronto. L'operazione O (n ^ 2) sarà più veloce per i piccoli insiemi di dati. Ma quando n = 1000, e si sta facendo 5000 radici quadrate, ma 1000000 confronti, poi la O (n) potrebbe iniziare a guardare meglio.

Altri suggerimenti

Credo che la maggior parte delle persone sono d'accordo prima è O (n ^ 2). ciclo esterno viene eseguito n volte e corre ciclo interni n volte ogni scadere del tempo ciclo esterno. Quindi il tempo di esecuzione è O (n * n), O (n ^ 2).

Il secondo è O (n ^ 2) perché le piste ciclo esterno n volte. I cicli interni corre volte n-1. In media per questo algoritmo, ciclo interno viene eseguito n / 2 volte per ogni ciclo esterno. quindi il tempo di esecuzione di questo algoritmo è O (n * n / 2) => O (1/2 * n ^ 2) => O (n ^ 2).

notazione O-grande non dice nulla circa la velocità dell'algoritmo tranne che per la velocità con cui è relativo a se stesso quando la dimensione dei cambiamenti di ingresso.

Un algoritmo potrebbe essere O (1) ancora prendere un milione di anni. Un altro algoritmo potrebbe essere O (n ^ 2), ma essere più veloce di un (n) algoritmo O per le piccole n.

Alcune delle risposte a questa domanda può aiutare con questo aspetto della notazione O-grande. Le risposte a questa domanda può anche essere utile.

Ignorare il problema di chiamare il vostro output del programma "permutazione":

Big-O-notazione omette coefficienti costanti. E 2 è un coefficiente costante.

Quindi, non c'è nulla di male per i programmi di due volte più veloce rispetto all'originale per avere lo stesso O ()

Hai ragione. Due algoritmi sono equivalenti in notazione O-grande se uno di loro prende una quantità costante di tempo più ( "A prende 5 minuti più di B"), o un multiplo ( "A prende 5 volte più lungo di B") o entrambi ( "A richiede 2 volte B più ulteriori 30 millisecondi ") per tutte le dimensioni di ingresso.

Ecco un esempio che utilizza un algoritmo di fondamentalmente diverso di fare un simile tipo di problema. In primo luogo, la versione più lenta, che assomiglia molto a tuo esempio originale: 

boolean arraysHaveAMatch = false;
for (int i = 0; i < arr1.length(); i++) {
    for (int j = i; j < arr2.length(); j++) {
        if (arr1[i] == arr2[j]) {
            arraysHaveAMatch = true;
        }
    }
}

Che ha O (n ^ 2) il comportamento, proprio come l'originale (che utilizza anche la stessa scorciatoia hai scoperto di iniziare l'indice j dall'indice i anziché da 0). Ora qui è un approccio diverso: 

boolean arraysHaveAMatch = false;
Set set = new HashSet<Integer>();
for (int i = 0; i < arr1.length(); i++) {
    set.add(arr1[i]);
}
for (int j = 0; j < arr2.length(); j++) {
    if (set.contains(arr2[j])) {
        arraysHaveAMatch = true;
    }
}

Ora, se si tenta di correre questi, probabilmente troverete che la prima versione è più veloce. Almeno se si tenta con array di lunghezza 10. Poiché la seconda versione ha a che fare con la creazione dell'oggetto HashSet e tutte le sue strutture dati interne, e perché deve calcolare un codice hash per ogni intero. Tuttavia, se lo provate con array di lunghezza 10.000.000 troverete una storia completamente diversa. La prima versione deve esaminare circa 50.000.000.000.000 coppie di numeri (circa (N * N) / 2); la seconda versione deve eseguire calcoli di funzioni hash su circa 20.000.000 numeri (circa 2 * N). In questo caso, si vuole sicuramente la seconda versione !!

L'idea di base dietro i calcoli Big O è (1) è abbastanza facile da calcolare (non dovete preoccuparvi di dettagli come quanto velocemente il vostro CPU è o che tipo di cache L2 ha), e (2) che si preoccupa per i piccoli problemi ... sono abbastanza veloce in ogni caso: è il problema grande che ti ucciderà! Questi non sono sempre il caso (a volte non importa che tipo di cache di che hai, e, talvolta, non importa quanto bene le cose si esibiscono su piccoli insiemi di dati), ma sono abbastanza vicino al vero abbastanza spesso per i Big O per essere utile.

Hai ragione su entrambi essendo O-grande n al quadrato, e in realtà dimostrato che per essere vero nella tua domanda quando hai detto "Ora, questo algoritmo è due volte più veloce rispetto all'originale. " Due volte più veloce mezzi moltiplicati per 1/2, che è una costante, quindi, per definizione, sono nello stesso set O-grande.

Un modo di pensare a Big O è quello di considerare quanto bene i vari algoritmi sarebbero cavata anche in circostanze davvero ingiusto. Per esempio, se uno è stato eseguito su un davvero potente supercomputer e l'altro è stato eseguito su un orologio da polso. Se è possibile scegliere una N che è così grande che, anche se l'algoritmo peggio è in esecuzione su un supercomputer, l'orologio da polso può ancora finire prima, poi hanno differenti complessità Big O. Se, d'altra parte, si può vedere che il supercomputer vincerà sempre, indipendentemente da quale algoritmo si è scelto o quanto è grande la N è stato, quindi entrambi gli algoritmi necessario, per definizione, hanno la stessa complessità.

In algoritmi, l'algoritmo più veloce è stato solo due volte più veloce come il primo. Questo non è abbastanza di un vantaggio per l'orologio da polso per battere il supercomputer, anche se N è stata molto alta, 1 milione, 1trillion, o anche il numero di Graham, l'orologio da tasca potrebbe mai battere il super computer con tale algoritmo. Lo stesso sarebbe vero se si scambiano di algoritmi. Pertanto entrambi gli algoritmi, per definizione di Big O, hanno la stessa complessità.

Si supponga che ho avuto un algoritmo per fare la stessa cosa a O ( n ) tempo. Ora immagino anche che ti ho dato un array di 10000 caratteri. I suoi algoritmi prenderebbero n n ^ 2 ^ tempo 2 e (1/2), che è 100.000.000 e 50.000.000. Il mio algoritmo avrebbe preso 10.000. Chiaramente quel fattore di 1/2, non sta facendo la differenza, dal momento che il mio è molto più veloce. n ^ 2 termine si dice dominano i termini minori come n e 1/2, essenzialmente rendendoli trascurabile.

La grande-oh notazione esprimere una famiglia di funzioni, in modo da dire "questa cosa è O (n²)" mezzi non

Non è pedanteria, è l'unico modo corretto per capire queste cose.

O (f) = {g | esiste x_0 e c tale che, per ogni x> x_0, g (x) <= f (x) * c}

Ora, supponiamo che si sta contando i passi che il vostro algoritmo, nel peggiore dei casi , fa in termini di dimensioni dell'ingresso: chiamare tale funzione f. Se f \ in O (n²), allora si può dire che l'algoritmo ha un caso peggiore di O (n²) (ma anche O (n³) o O (2 ^ n)). La mancanza di significato delle costanti seguono dalla definizione (vedere che c?).

Il modo migliore per capire la notazione O-grande è quello di ottenere la comprensione della matematica l'idea dietro la notazione. Cercare dizionario significato della parola "Asymptote" 

A line which approaches nearer to some curve than assignable distance, but, though
infinitely extended, would never meet it.

Questo definisce il tempo massimo di esecuzione (immaginario perché la linea asintoto incontra la curva all'infinito), così che cosa mai si fa sarà sotto quel tempo.
Con questa idea, si potrebbe desiderare di sapere, O-grande, piccola O e la notazione omega.

Tenete sempre a mente, notazione O-grande rappresenta lo scenario "worst case". Nel tuo esempio, il primo algoritmo ha un caso medio di pieno anello interno anello * pieno esterno, quindi è n ^ 2 naturalmente. Poiché il secondo caso è un caso dove è quasi pieno esterno anello * completo ciclo interno, deve essere concentrati nella stessa pila di n ^ 2, dal momento che è il suo caso peggiore. Da lì si ottiene solo meglio, e la vostra media rispetto alla prima funzione è molto più basso. Indipendentemente da ciò, come n cresce, il tuo tempo funzioni cresce in modo esponenziale, e questo è tutto Big O davvero ti dice. Le curve esponenziali possono variare ampiamente, ma alla fine della giornata, sono tutti dello stesso tipo.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top