Esempi pratici in Java della notazione Big O

1. Panoramica

In questo tutorial, parleremo di cosa significa Big O Notation. Esamineremo alcuni esempi per esaminare il suo effetto sul tempo di esecuzione del codice.

2. L'intuizione della notazione Big O

Sentiamo spesso le prestazioni di un algoritmo descritto utilizzando la notazione Big O.

Lo studio delle prestazioni degli algoritmi - o complessità algoritmica - rientra nel campo dell'analisi degli algoritmi. L'analisi dell'algoritmo risponde alla domanda su quante risorse, come lo spazio su disco o il tempo, consuma un algoritmo.

Considereremo il tempo come una risorsa. In genere, meno tempo richiede un algoritmo per il completamento, meglio è.

3. Algoritmi a tempo costante - O (1)

In che modo questa dimensione di input di un algoritmo influisce sul suo tempo di esecuzione? La chiave per comprendere Big O è capire la velocità con cui le cose possono crescere. Il tasso in questione qui è il tempo impiegato per dimensione di input.

Considera questo semplice pezzo di codice:

int n = 1000; System.out.println("Hey - your input is: " + n);

Chiaramente, non importa cosa n sia, sopra. L'esecuzione di questo pezzo di codice richiede una quantità di tempo costante. Non dipende dalla dimensione di n.

Allo stesso modo:

int n = 1000; System.out.println("Hey - your input is: " + n); System.out.println("Hmm.. I'm doing more stuff with: " + n); System.out.println("And more: " + n);

L'esempio sopra è anche tempo costante. Anche se impiega 3 volte il tempo per funzionare, non dipende dalla dimensione dell'ingresso, n. Indichiamo algoritmi a tempo costante come segue: O (1) . Nota che O (2) , O (3) o anche O (1000) significherebbe la stessa cosa.

Non ci interessa esattamente quanto tempo ci vuole per correre, solo che ci vuole tempo costante.

4. Algoritmi temporali logaritmici - O (log n)

Gli algoritmi a tempo costante sono (asintoticamente) i più veloci. Il tempo logaritmico è il successivo più veloce. Sfortunatamente, sono un po 'più complicati da immaginare.

Un esempio comune di algoritmo temporale logaritmico è l'algoritmo di ricerca binaria. Per vedere come implementare la ricerca binaria in Java, fare clic qui.

Ciò che è importante qui è che il tempo di esecuzione cresce in proporzione al logaritmo dell'input (in questo caso, log in base 2):

for (int i = 1; i < n; i = i * 2){ System.out.println("Hey - I'm busy looking at: " + i); }

Se n è 8, l'output sarà il seguente:

Hey - I'm busy looking at: 1 Hey - I'm busy looking at: 2 Hey - I'm busy looking at: 4

Il nostro semplice algoritmo ha eseguito log (8) = 3 volte.

5. Algoritmi di tempo lineare - O (n)

Dopo gli algoritmi del tempo logaritmico, otteniamo la classe successiva più veloce: gli algoritmi del tempo lineare.

Se diciamo che qualcosa cresce linearmente, intendiamo che cresce direttamente proporzionale alla dimensione dei suoi input.

Pensa a un semplice ciclo for:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); }

Quante volte viene eseguito il ciclo for? n volte, ovviamente! Non sappiamo esattamente quanto tempo ci vorrà per farlo funzionare - e non ci preoccupiamo di questo.

Quello che sappiamo è che il semplice algoritmo presentato sopra crescerà linearmente con la dimensione del suo input.

Preferiremmo un tempo di esecuzione di 0.1n rispetto a (1000n + 1000) , ma entrambi sono ancora algoritmi lineari; entrambi crescono direttamente in proporzione alla dimensione dei loro input.

Anche in questo caso, se l'algoritmo è stato modificato come segue:

for (int i = 0; i < n; i++) { System.out.println("Hey - I'm busy looking at: " + i); System.out.println("Hmm.. Let's have another look at: " + i); System.out.println("And another: " + i); }

Il tempo di esecuzione sarebbe ancora lineare nella dimensione del suo input, n . Indichiamo algoritmi lineari come segue: O (n) .

Come per gli algoritmi a tempo costante, non ci interessano le specifiche del runtime. O (2n + 1) è uguale a O (n) , poiché Big O Notation si occupa della crescita per le dimensioni degli input.

6. N Log N Time Algoritmi - O (n log n)

n log n è la prossima classe di algoritmi. Il tempo di esecuzione cresce in proporzione a n log n dell'input:

for (int i = 1; i <= n; i++){ for(int j = 1; j < n; j = j * 2) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

Ad esempio, se n è 8, questo algoritmo verrà eseguito 8 * log (8) = 8 * 3 = 24 volte. Se abbiamo o meno una disuguaglianza rigida nel ciclo for è irrilevante ai fini di una notazione O grande.

7. Algoritmi temporali polinomiali - O (np)

Successivamente abbiamo algoritmi di tempo polinomiale. Questi algoritmi sono anche più lenti di n log n algoritmi.

Il termine polinomio è un termine generale che contiene funzioni quadratiche (n2) , cubiche (n3) , quartiche (n4) , ecc. Quello che è importante sapere è che O (n2) è più veloce di O (n3) che è più veloce di O (n4) , ecc.

Let's have a look at a simple example of a quadratic time algorithm:

for (int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { System.out.println("Hey - I'm busy looking at: " + i + " and " + j); } } 

This algorithm will run 82 = 64 times. Note, if we were to nest another for loop, this would become an O(n3) algorithm.

8. Exponential Time Algorithms – O(kn)

Now we are getting into dangerous territory; these algorithms grow in proportion to some factor exponentiated by the input size.

For example, O(2n) algorithms double with every additional input. So, if n = 2, these algorithms will run four times; if n = 3, they will run eight times (kind of like the opposite of logarithmic time algorithms).

O(3n) algorithms triple with every additional input, O(kn) algorithms will get k times bigger with every additional input.

Let's have a look at a simple example of an O(2n) time algorithm:

for (int i = 1; i <= Math.pow(2, n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

This algorithm will run 28 = 256 times.

9. Factorial Time Algorithms – O(n!)

In most cases, this is pretty much as bad as it'll get. This class of algorithms has a run time proportional to the factorial of the input size.

A classic example of this is solving the traveling salesman problem using a brute-force approach to solve it.

An explanation of the solution to the traveling salesman problem is beyond the scope of this article.

Instead, let's look at a simple O(n!) algorithm, as in the previous sections:

for (int i = 1; i <= factorial(n); i++){ System.out.println("Hey - I'm busy looking at: " + i); }

where factorial(n) simply calculates n!. If n is 8, this algorithm will run 8! = 40320 times.

10. Asymptotic Functions

Big O is what is known as an asymptotic function. All this means, is that it concerns itself with the performance of an algorithm at the limit – i.e. – when lots of input is thrown at it.

Big O doesn't care about how well your algorithm does with inputs of small size. It's concerned with large inputs (think sorting a list of one million numbers vs. sorting a list of 5 numbers).

Another thing to note is that there are other asymptotic functions. Big Θ (theta) and Big Ω (omega) also both describes algorithms at the limit (remember, the limit this just means for huge inputs).

To understand the differences between these 3 important functions, we first need to know that each of Big O, Big Θ, and Big Ω describes a set (i.e., a collection of elements).

Here, the members of our sets are algorithms themselves:

  • Big O describes the set of all algorithms that run no worse than a certain speed (it's an upper bound)
  • Conversely, Big Ω describes the set of all algorithms that run no better than a certain speed (it's a lower bound)
  • Infine, Big Θ descrive l'insieme di tutti gli algoritmi che funzionano a una certa velocità (è come l'uguaglianza)

Le definizioni che abbiamo messo sopra non sono matematicamente accurate, ma aiuteranno la nostra comprensione.

Di solito, sentirai cose descritte usando Big O , ma non fa male sapere di Big Θ e Big Ω.

11. Conclusione

In questo articolo abbiamo discusso della notazione Big O e di come la comprensione della complessità di un algoritmo possa influire sul tempo di esecuzione del codice.

Una grande visualizzazione delle diverse classi di complessità può essere trovata qui.

Come al solito, gli snippet di codice per questo tutorial possono essere trovati su GitHub.