Dove trovare cosa significa O (n^2) e O (n) etc?

Question

Ho notato delle risposte allo stack overflow che usano termini come questi, ma non so cosa significano. Come si chiamano e c'è una buona risorsa che può spiegarli in termini semplici?

Answer 1

Quella notazione è chiamata Big O notation, ed è usato come una scorciatoia per esprimere la complessità algoritmica (in pratica quanto tempo un determinato algorithim avrà per l'esecuzione come la dimensione di ingresso (n) cresce)

In generale, ti eseguito nelle seguenti principali tipi di algorithims:

1. O (1) - costante - la lunghezza del tempo che questo algorithim necessario per completare non dipende dal numero di elementi che l'algorithim deve processare.
2. O (log n) - Logaritmico - Il tempo che questo algoritmo impiega per completare dipende dal numero di elementi che l'algoritmo deve elaborare. Quando la dimensione dell'ingresso diventa più grande, è necessario meno tempo per ogni nuovo input.
3. O (n) - Lineare - Il tempo che questo algoritmo impiega per completare dipende direttamente dal numero di elementi che l'algoritmo deve elaborare. Man mano che le dimensioni dell'input crescono, il tempo necessario aumenta in quantità uguali.
4. O (n^2) - Polinominale: con l'aumentare delle dimensioni dell'ingresso, il tempo necessario per elaborare l'input aumenta di un numero sempre maggiore, il che significa che le dimensioni di input di grandi dimensioni diventano proibitive.
5. O (2^n) - Esponenziale - I tipi più complicati di problemi. Il tempo di elaborare aumenta in base alle dimensioni dell'input in misura estrema.

In genere è possibile ottenere una valutazione approssimativa della complessità di un algoritmo osservando come viene utilizzato. Per esempio, guardando il seguente metodo:

function sum(int[] x) { 
    int sum = 0; 
    for (int i = 0; i < x.length; i++) { 
     sum += x[i]; 
    } 
    return sum; 
} 

Ci sono alcune cose che devono essere fatte qui:

• inizializzare una variabile denominata somma
• inizializzare una variabile denominata I
• Per ogni iterazione di i: Aggiungi x [i] per sommare, aggiungi 1 a i, controlla se i è minore di x.lunghezza
• somma di ritorno

Ci sono alcune operazioni che vengono eseguite in tempo costante qui (i primi due e l'ultimo), dal momento che la dimensione di x non inciderebbe quanto tempo impiegano per l'esecuzione. Inoltre, ci sono alcune operazioni che vengono eseguite in tempo lineare (poiché vengono eseguite una volta per ogni voce in x). Con notazione O-grande, l'algorithim è semplificata al più complesso, in modo da questa somma algorithim verrebbe eseguito nel O (n)

Answer 2

Leggi prima il Computational Complexity, quindi prova alcuni libri sugli algoritmi come Introduction to Algorithms.

Dalla pagina di Wikipedia:

notazione O-grande caratterizza funzioni secondo i loro tassi di crescita

Se non sarà di non forare i dettagli si può molto spesso approssimativa complessità algoritmo analizzando il suo codice:

void simpleFunction(arg); // O(1) - if number of function instructions is constant and don't depend on number of input size 

for (int i=0;i<n;i++) {simpleFunction(element[i]);} // O(n) 

for (int i=0;i<n;i++) { // this one runs O(n^2) 
    for (int j=0;j<n;j++) { 
     simpleFunction(element[i]); 
    } 
} 

for (int i=0;i<n;i*=2) { // O(lgn) 
    simpleFunction(element[i]); 
} 

A volte non è così semplice stimare la funzione/algoritmo grande complessità di notazione O in suc h casi viene utilizzato amortized analysis. Sopra il codice dovrebbe servire solo come QuickStart.

Answer 3

Questo è chiamato il Big O notation e viene utilizzato per quantificare la complessità degli algoritmi.

O (1) significa che l'algoritmo richiede un tempo costante indipendentemente dalla quantità di dati da elaborare.

O (n) significa che la velocità dell'algoritmo cresce in modo lineare con la quantità di dati.

e così via ...

Così il basso è il potere di n nella notazione O meglio il vostro algoritmo è quello di risolvere il problema. Il caso migliore è O (1) (n = 0). Ma c'è una complessità intrinseca in molti problemi, quindi in quasi tutti i casi non troverete un algoritmo così ideale.

Answer 4

Le risposte sono buone finora. Il termine principale per la ricerca sul Web è "Notazione Big O".

L'idea alla base della matematica di "someformula is O (someterm)" è che, quando la variabile va all'infinito, "someterm" è la parte della formula che domina.

Ad esempio, si supponga di avere 0.05*x^3 + 300*x^2 + 200000000*x + 10. Per dimensioni molto basse di x (x == 1 o x == 2), quello 200000000*x sarà di gran lunga la parte più grande. A quel punto una trama della formula apparirà lineare. Mentre procedete, ad un certo punto la parte 300*x^2 sarà più grande. Tuttavia, se continui a rendere x ancora più grande, grande quanto ti interessa, la parte 0.05*x^3 sarà la più grande e alla fine supererà completamente le altre parti della formula. È qui che diventa chiaro da un grafico che si sta osservando una funzione a cubetti. Quindi diremmo che la formula è O(x^3).