Algoritmi - Complessita'

1. Complessità Possibili
2. Complessità O(\(n\))
- 2.1. Ricorsione su meta' elementi con costo di dimezzamento n ( relazione 3 )
- 2.2. Ricosione su entrambe le metà con costo di divisione divisione unitario ( relazione 5 )
3. Complessita' O(n²)
- 3.1. Ricorsione su n-1 elementi con costo di divisione pari a n ( relazione 1 )
4. Complessita' (\(log_2 n\))
5. Complessita' (\(nlog_2 n\))

1. Complessità Possibili

Come concetti di base il costo e' riferito

Complessità del tipo O(\(n\))
1. la ricorsione su meta' elementi con costo di divisione n ( relazione 3 );
2. la ricosione su entrambe le metà con costo di divisione divisione unitario ( relazione 5 );
Complessita' del tipo O(\(n^2\))
1. ricorsione su n-1 elementi con costo di divisione pari a n ( relazione 1 o ricerca sequenziale );
Complessita' O(\(nlog_2 n\))
1. ricorsione su entrambe le meta degli elementi con costo di divisione n ( relazione 4 );
Complessita' O(\(log_2 n\))
1. ricorsione su metà input con costo di divisione unitario ( relazione 2 o ricerca binaria )

2. Complessità O(\(n\))

Numero di elementi totali e 2^N

2.1. Ricorsione su meta' elementi con costo di dimezzamento n ( relazione 3 )

Somma dei primi n numeri.

           [0:7] (n=8, costo: O(1))
          /       \
     [0:3]         [4:7] (n=4, costo: O(1))
     /    \        /    \
 [0:1]   [2:3]  [4:5]   [6:7] (n=2, costo: O(1))
  / \     / \    / \     / \
[0][1] [2][3] [4][5] [6][7] (n=1, O(1)×8)

Passo	Costo del passo	Costo Parziale del fino all' n-esimo passo	Nota matematica
1	C(n)=2^N	C(n)=2^N
2	C(n/2)=2^N-1	C(n/2)=2^N+ 2^N-1
3	C(n/4)= 2^N-2	C(n/4)= 2^N + 2^N-1 + 2^N-2
…
n/(n-1)	C(n/)
n/n	C(n/n)	C(n/n)=2^N + 2^N-1 + 2^N-2 + …+ 1	il costo del passo è 2^N-N=2⁰=1
Costo Totale		C(n)=\(\sum_{i=1}^{N}2^i=\) serie geom. di raione q	q>1 somma di potenze
			q<1 la somma vale \(\frac{1}{q-1}\)
			q=1 sla somma vale n

2.2. Ricosione su entrambe le metà con costo di divisione divisione unitario ( relazione 5 )

Esplorazione degli elementi di un array mediante divisione binaria. Il costo dell'operazione di divisione e' sempre O(1)

        [A,B,C,D,E,F,G,H] (O(1))
        /               \
    [A,B,C,D]          [E,F,G,H] (O(1) + O(1))
     /     \            /     \
[A,B]    [C,D]      [E,F]    [G,H] (O(1)×4)
 / \      / \        / \      / \
[A][B]  [C][D]     [E][F]   [G][H] (8 casi base, O(1)×8)

3. Complessita' O(n²)

Numero di elementi totali e 2^N

3.1. Ricorsione su n-1 elementi con costo di divisione pari a n ( relazione 1 )

Somma di 4 numeri

[A,B,C,D] (O(4)) 
→ [A,B,C] (O(3)) 
  → [A,B] (O(2)) 
    → [A] (O(1)) 
     → [] (O(1)) 
      ← A (O(1)) 
    ← A+B (O(1)) 
  ← A+B+C (O(1)) 
← A+B+C+D (O(1))

4. Complessita' (\(log_2 n\))

Ricerca del numero 23

[2,5,8,12,16,23,38,56] (livello 0, O(1))
        |
      mid=12 (23 > 12 → cerca a destra)
        |
[16,23,38,56] (livello 1, O(1))
        |
      mid=38 (23 < 38 → cerca a sinistra)
        |
   [16,23] (livello 2, O(1))
        |
      mid=23 (trovato!)

5. Complessita' (\(nlog_2 n\))

Algoritmo di ordinamento di merge sort

Livello 0: [7,2,1,6,8,5,3,4] (n=8)
│
├─ Divisione: O(1) → [7,2,1,6] | [8,5,3,4]
│
├─ Livello 1: [7,2,1,6] (n=4)
│  │
│  ├─ Divisione: O(1) → [7,2] | [1,6]
│  │
│  ├─ Livello 2: [7,2] (n=2)
│  │  │
│  │  ├─ Divisione: O(1) → [7] | [2]
│  │  │
│  │  ├─ Foglia: [7] (costo O(1))
│  │  ├─ Foglia: [2] (costo O(1))
│  │  │
│  │  └─ Merge: O(2) → [2,7]
│  │
│  ├─ Livello 2: [1,6] (n=2)
│  │  (stessa struttura → merge O(2) → [1,6])
│  │
│  └─ Merge: O(4) → [1,2,6,7]
│
├─ Livello 1: [8,5,3,4] (n=4)
│  (stessa struttura → merge finale O(4) → [3,4,5,8])
│
└─ Merge finale: O(8) → [1,2,3,4,5,6,7,8]

Costi totali:

Divisioni: tutte le divisioni costano O(1) e sono già incluse nel costo del merge.
Merge: ogni livello ha merge per un totale di O(n):
1. Livello 2: 4 merge × O(2) = O(8)
2. Livello 1: 2 merge × O(4) = O(8)
3. Livello 0: 1 merge × O(8) = O(8)
Numero di livelli: log₂8 = 3 → O(log n).
Costo per livello O(n);
Costo totale O(n)xO(log n)=O(nlog n)