algorithm
Notazione Big-O

Osservazioni

Un ciclo semplice

La seguente funzione trova l'elemento massimo in un array:

int find_max(const int *array, size_t len) {
    int max = INT_MIN;
    for (size_t i = 0; i < len; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    return max;
}

La dimensione di input è la dimensione dell'array, che ho chiamato len nel codice.

Contiamo le operazioni.

int max = INT_MIN;
size_t i = 0;

Questi due compiti vengono eseguiti una sola volta, quindi sono 2 operazioni. Le operazioni che sono in loop sono:

if (max < array[i])
i++;
max = array[i]

Dato che ci sono 3 operazioni nel ciclo, e il ciclo è fatto n volte, aggiungiamo 3n alle nostre 2 operazioni già esistenti per ottenere 3n + 2 . Quindi la nostra funzione richiede 3n + 2 operazioni per trovare il massimo (la sua complessità è 3n + 2 ). Questo è un polinomio in cui il termine in più rapida crescita è un fattore di n, quindi è O (n).

Probabilmente hai notato che "operazione" non è molto ben definita. Per esempio ho detto che if (max < array[i]) era una operazione, ma a seconda dell'architettura questa istruzione può compilare ad esempio tre istruzioni: una lettura di memoria, un confronto e un ramo. Ho anche considerato tutte le operazioni come uguali, anche se ad esempio le operazioni di memoria saranno più lente delle altre e le loro prestazioni varieranno in modo selvaggio, ad esempio per gli effetti di cache. Ho anche completamente ignorato la dichiarazione return, il fatto che verrà creata una cornice per la funzione, ecc. Alla fine non ha importanza per l'analisi della complessità, perché qualunque sia il modo in cui scelgo di contare le operazioni, cambierà solo il coefficiente del fattore n e della costante, quindi il risultato sarà ancora O (n). La complessità mostra come l'algoritmo scala con le dimensioni dell'input, ma non è l'unico aspetto della performance!

Un ciclo nidificato

La seguente funzione controlla se un array ha duplicati prendendo ogni elemento, quindi iterando sull'intero array per vedere se l'elemento è presente

_Bool contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len; j++) {
            if (i != j && array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

Il ciclo interno esegue ad ogni iterazione un numero di operazioni che è costante con n . Il ciclo esterno esegue anche alcune operazioni costanti e esegue il ciclo interno n volte. Il ciclo esterno stesso viene eseguito n volte. Quindi le operazioni all'interno del ciclo interno vengono eseguite n^2 volte, le operazioni nel ciclo esterno vengono eseguite n volte e l'assegnazione a i viene eseguita una volta. Quindi, la complessità sarà qualcosa come an^2 + bn + c , e poiché il termine più alto è n^2 , la notazione O(n^2) è O(n^2) .

Come avrai notato, possiamo migliorare l'algoritmo evitando di fare gli stessi confronti più volte. Possiamo iniziare da i + 1 nel ciclo interno, poiché tutti gli elementi prima di esso saranno già stati confrontati con tutti gli elementi dell'array, incluso quello all'indice i + 1 . Questo ci permette di abbandonare il controllo i == j .

_Bool faster_contains_duplicates(const int *array, size_t len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (array[i] == array[j]) {
                return 1;
            }
        }
    }
    return 0;
}

Ovviamente, questa seconda versione fa meno operazioni e quindi è più efficiente. Come si traduce in notazione Big-O? Bene, ora il corpo del ciclo interno viene eseguito 1 + 2 + ... + n - 1 = n(n-1)/2 volte. Questo è ancora un polinomio di secondo grado, e quindi è ancora solo O(n^2) . Abbiamo chiaramente ridotto la complessità, dal momento che abbiamo diviso approssimativamente per 2 il numero di operazioni che stiamo facendo, ma siamo ancora nella stessa classe di complessità definita da Big-O. Per ridurre la complessità a una classe inferiore, dovremmo dividere il numero di operazioni per qualcosa che tende all'infinito con n .

Un esempio di O (log n)

introduzione

Si consideri il seguente problema:

L è una lista ordinata che contiene n interi con segno ( n è abbastanza grande), per esempio [-5, -2, -1, 0, 1, 2, 4] (qui, n ha un valore di 7). Se L è noto per contenere l'intero 0, come puoi trovare l'indice di 0?

Approccio naïve

La prima cosa che viene in mente è quella di leggere ogni indice fino a trovare 0. Nel peggiore dei casi, il numero di operazioni è n , quindi la complessità è O (n).

Funziona bene per piccoli valori di n , ma esiste un modo più efficiente?

Dicotomia

Considera il seguente algoritmo (Python3):

a = 0
b = n-1
while True:
  h = (a+b)//2 ## // is the integer division, so h is an integer
  if L[h] == 0:
    return h
  elif L[h] > 0:
    b = h
  elif L[h] < 0:
    a = h

a e b sono gli indici tra cui 0 deve essere trovato. Ogni volta che entriamo nel ciclo, usiamo un indice tra a e b e lo usiamo per restringere l'area da cercare.

Nel peggiore dei casi, dobbiamo aspettare fino a quando a e b sono uguali. Ma quante operazioni richiede? Non n, perché ogni volta che entriamo nel ciclo, dividiamo la distanza tra a e b di circa due. Piuttosto, la complessità è O (log n).

Spiegazione

Nota: quando scriviamo "log", intendiamo il logaritmo binario, o log base 2 (che scriveremo "log_2"). Come O (log_2 n) = O (log n) (puoi fare la matematica) useremo "log" invece di "log_2".

Chiamiamo x il numero di operazioni: sappiamo che 1 = n / (2 ^ x).

Quindi 2 ^ x = n, quindi x = registro n

Conclusione

Di fronte alle divisioni successive (sia per due che per qualsiasi numero), ricorda che la complessità è logaritmica.

O (log n) tipi di Algoritmi

Diciamo che abbiamo un problema di dimensioni n. Ora per ogni passo del nostro algoritmo (che abbiamo bisogno di scrivere), il nostro problema originale diventa la metà della sua dimensione precedente (n / 2).

Quindi ad ogni passo, il nostro problema diventa mezzo.

Quando lo spazio del problema è ridotto (cioè risolto completamente), non può essere ulteriormente ridotto (n diventa uguale a 1) dopo aver chiuso la condizione di controllo.

1. Diciamo al punto k o al numero di operazioni:

   problem-size = 1

2. Ma sappiamo al passo k, la nostra dimensione del problema dovrebbe essere:

   problema-dimensione = n / 2 ^k

3. Da 1 a 2:

   n / 2 ^k = 1 o

   n = 2 ^k

4. Prendi il registro da entrambi i lati

   log _e n = k log _e 2

   o

   k = log _e n / log _e 2

5. Utilizzando il log della formula _x m / log _x n = log _n m

   k = log ₂ n

   o semplicemente k = log n

Ora sappiamo che il nostro algoritmo può funzionare al massimo fino al log n, quindi la complessità del tempo arriva come
O (log n)

Un esempio molto semplice nel codice per supportare il testo sopra è:

for(int i=1; i<=n; i=i*2)
{
    // perform some operation
}

Così ora se qualcuno ti chiede se n è 256 quanti passi quel ciclo (o qualsiasi altro algoritmo che abbatte la dimensione del problema in metà) verrà eseguito puoi facilmente calcolare.

k = log ₂ 256

k = log ₂ 2 ⁸ (=> log _a a = 1)

k = 8

Un altro ottimo esempio per un caso simile è l' algoritmo di ricerca binaria .

int bSearch(int arr[],int size,int item){
 int low=0;
 int high=size-1;

 while(low<=high){                 
     mid=low+(high-low)/2;                 
     if(arr[mid]==item)                        
         return mid;                 
     else if(arr[mid]<item)                         
         low=mid+1;                
     else  high=mid-1;      
     }  
  return –1;// Unsuccessful result
}