La complessita asintotica si puo spiegare solo tramite esempi. Essendo alle superiori non devi preoccuparti di andare troppo nei dettagli, ma e' giusto sapere a grandi linee come funziona essendo uno strumento essenziale per calcolare l'efficienza di un algoritmo che stai scrivendo o che e' gia stato ideato e lo stai studiando.
Esempio, una semplice ricerca lineare di un array A con n elementi :
for(int i=0;i < A.length; ++i){
System.out.println(A[i]);
}
Questo ciclo avra complessita O(n) perche iteri n volte su un totale di n elementi nell'array A. E' importante escludere le costanti nel calcolo della complessita, esempio :
for(int i=0;i < A.length; ++i){
System.out.println(A[i]);
}
for(int i=0;i < A.length; ++i){
System.out.println(A[i]);
}
Siccome svolgiamo lo stesso lavoro di prima saresti tentato a dire O(2n), ma nel calcolo totale escludiamo le costanti quindi sara sempre O(n).
Se non conosci la dimensione totale degli arrays con cui hai a che fare, attenzione :
for(int i=0;i < A.length; ++i){
System.out.println(A[i]);
}
for(int i=0;i < B.length; ++i){
System.out.println(B[i]);
}
Questo avra complessita O(a+b) supponendo che a e' la quantita di element in A e b la quantia di elementi in B. Se fossero annidati :
for(int i=0;i < A.length; ++i){
System.out.println(A[i]);
for(int i=0;i < B.length; ++i){
System.out.println(B[i]);
}
}
La complessita diventerebbe O(ab). Le complessita del tipo O(logN) sono diverse, in particolare ricordati che nel calcolo della complessita asintotica di un algoritmo la base del logaritmo non ha significato, che sia 2, 3, 10, e' lo stesso. Per capirla puoi pensare al famoso algoritmo "binarySearch" che ha complessita O(logn).
In binarySearch si cerca un elemento in un array ordinato :
Obbiettivo : cerca x in {1,2,3,...,n} , chiamiamo l'array A
funzione binarySearch(array, elementoDaTrovare)
confronta con x con l'elemento in mezzo all'array (indice mid = A.length/2)
se x == A[mid], abbiamo trovato x
se x < A[mid] allora x sara per forza nel sub-array sinistro
se x > A[mid] allora x sara per forza nel sub-array destro
public int runBinarySearchIteratively(
int[] sortedArray, int key, int low, int high) {
int index = Integer.MAX_VALUE;
while (low <= high) {
int mid = (low + high) / 2;
if (sortedArray[mid] < key) {
low = mid + 1;
} else if (sortedArray[mid] > key) {
high = mid - 1;
} else if (sortedArray[mid] == key) {
index = mid;
break;
}
}
return index;
}
Il tempo totale rappresenta quindi quanti passi (quante volte divido A.length) dobbiamo fare affinche mid diventi 1, esempio con A.length = 16.
N=16
[diviso 2]N=8
[diviso 2]N=4
[diviso 2]N=2
[diviso 2]N=1
Ho diviso per 2 quattro volte quindi , 2^4 = 16 ma allora log16 = 4 quindi O(log16) quindi O(logn) dove n e' il nostro A.length.
Questa spiegazione e' semplicistica ma ti da almeno un'idea di come funzioni la complessita. Se vuoi andare oltre ti consiglio di scaricarti (lo trovi anche gratis), "cracking the coding interview" di Gayle Laakmann McDowell.