Complessità Algoritmica

// Accedere a un elemento di un array → O(1)
int x = arr[5];       // Sempre 1 operazione, indipendentemente da |arr|

// Push/pop su uno stack → O(1)
stack[top++] = valore;

// Operazioni matematiche → O(1)
int somma = a + b;
double area = 3.14 * r * r;

// Hash map lookup (caso medio) → O(1)

// Ricerca binaria: a ogni iterazione taglia a metà
int binary_search(int arr[], int n, int target) {
    int sx = 0, dx = n - 1;
    while (sx <= dx) {
        int mid = sx + (dx - sx) / 2;  // Evita overflow
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) sx = mid + 1;
        else dx = mid - 1;
    }
    return -1;
}
// Con N=1.000.000: al massimo log₂(1.000.000) ≈ 20 iterazioni!

// Cerca il massimo → deve vedere tutti gli N elementi
int trova_max(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {   // Esegue n-1 volte
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

// Somma di tutti gli elementi → O(n)
long somma(int arr[], int n) {
    long s = 0;
    for (int i = 0; i < n; i++) s += arr[i];
    return s;
}

// Merge Sort divide il problema a metà ricorsivamente (log n livelli)
// e ad ogni livello fa O(n) lavoro → totale O(n log n)
void merge_sort(int arr[], int sx, int dx) {
    if (sx >= dx) return;
    int mid = (sx + dx) / 2;
    merge_sort(arr, sx, mid);    // Divide a sinistra  → log n livelli
    merge_sort(arr, mid+1, dx);  // Divide a destra
    merge(arr, sx, mid, dx);     // Unisce → O(n) per livello
}

// Bubble Sort: due cicli annidati → O(n²)
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {           // n-1 volte
        for (int j = 0; j < n-i-1; j++) {     // n-i-1 volte
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp;
            }
        }
    }
}
// Con n=1000: ~500.000 confronti
// Con n=10000: ~50.000.000 confronti (lento!)

// Fibonacci ricorsivo naive: ogni chiamata fa 2 chiamate ricorsive
long long fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // Albero binario di profondità n → 2^n nodi
}
// fib(10)  → 177 chiamate
// fib(30)  → 2.692.537 chiamate
// fib(50)  → ~2^50 = 1.125.899.906.842.624 chiamate → ANNI di attesa!

// REGOLA 1: Ignora le costanti
// f(n) = 3n + 5 → O(n)   (non O(3n+5))
for (int i = 0; i < 3*n; i++) { ... }   // O(n)
x = a + b + c + d;                       // O(1) (non O(4))

// REGOLA 2: Istruzioni consecutive → si sommano (prendi il più grande)
for (int i = 0; i < n; i++) { ... }     // O(n)
for (int i = 0; i < n*n; i++) { ... }   // O(n²)
// Totale: O(n) + O(n²) = O(n²)

// REGOLA 3: Cicli annidati → si moltiplicano
for (int i = 0; i < n; i++) {           // O(n)
    for (int j = 0; j < n; j++) {       // O(n) × O(n) = O(n²)
        ...
    }
}

// REGOLA 4: Ciclo che dimezza → logaritmico
int i = n;
while (i > 1) { i /= 2; }              // O(log n)

// REGOLA 5: Funzione ricorsiva con 2 chiamate → O(2^profondità)
void f(int n) {
    if (n == 0) return;
    f(n-1); f(n-1);                     // O(2ⁿ)
}

// REGOLA 6: Ricorsione che dimezza
void g(int n) {
    if (n == 0) return;
    g(n/2);                             // O(log n)
}

// ESEMPIO COMPLESSO: Qual è la complessità?
void esempio(int arr[], int n) {
    // Parte 1: O(n)
    for (int i = 0; i < n; i++) printf("%d", arr[i]);

    // Parte 2: O(n²)
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            printf("%d %d", arr[i], arr[j]);

    // Parte 3: O(log n)
    int k = 1;
    while (k < n) k *= 2;
}
// Totale: O(n) + O(n²) + O(log n) = O(n²)

// Bubble Sort: O(1) spazio aggiuntivo (in-place)
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp;  // Solo 1 variabile tmp
            }
}

// Merge Sort: O(n) spazio aggiuntivo (serve array temporaneo)
void merge(int arr[], int sx, int mid, int dx) {
    int *tmp = malloc((dx - sx + 1) * sizeof(int));  // Alloca O(n) spazio
    // ... merge logic ...
    free(tmp);
}

// Fibonacci ricorsivo: O(n) spazio (stack di chiamate profondo n)
long long fib_ricorsivo(int n) {
    if (n <= 1) return n;
    return fib_ricorsivo(n-1) + fib_ricorsivo(n-2);  // Stack profondo n
}

// Fibonacci iterativo: O(1) spazio
long long fib_iterativo(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;  // Solo 2 variabili!
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b; b = c;
    }
    return b;
}