Per l'analisi delle complessità ci baseremo sempre sulla lunghezza dell'input
Calcoliamo le complessità vengono valutate nei casi pessimi, per i casi medi è troppo sbatti calcolarsi le probabilità.
-
logaritmi:
-
serie aritmetiche:
$\sum ^n {K=1} \frac{1}{k} \simeq log(n)$ $\sum^{log(n)}{i=1}2^i \simeq n$
Disclamer: abuso di notazione. Nelle precedenti righe, e nel resto del corso, vengono utilizzati i simboli $=$ piuttosto che i simboli $\in$ (più corretti).* Piccolo extra: l'asintotico (di Analisi 1 per intenderci) è un caso particolare del $\Theta$. Quest'ultimo simbolo infatti ci dice che una funzione è comprimibile tra due coefficienti moltiplicativi di un'altra.
Nella crescita esponenziale, la base conta un sacco.
I casi ottimi li sanno fare tutti, siete ad ingegneria considerate sempre i casi pessimi.
nota che ci sono diverse versioni del MT che differiscono in base alla 'garanzia che danno' soprattutto nel caso 2
Utile teorema per valutare complessità del tipo:
I 3 casi, con K =
- se
allora - se
allora . La versione alternativa è che se allora - se
allora controllo che sia valida per qualche e per tutti gli grandi a sufficienza. In caso affermativo
Il Master Theorem non si può applicare nel caso in cui
Nel caso in cui
Tre fasi:
0) Faccio a mano un paio di iterazioni di
- Intuisco sbattendo la testa sul foglio una possibile soluzione
- Maggioro la
con la mia ipotesi : - Dimostro la veridicità della disequazione sostituendo la presunta soluzione nella l’equazione/disequazione alle ricorrenze:
esempio:
- intuisco
- maggioro
- sostituisco (la mia ipotesi induttiva) e verifico
per una
L’albero di ricorsione fornisce un aiuto per avere una congettura da verificare con il metodo di sostituzione. E' una rappresentazione delle chiamate ricorsive, indicando per ognuna la complessità. Ogni chiamata costituisce un nodo in un albero, i chiamati appaiono come figli del chiamante.
- Se
è accettato da una a nastri con complessità , per ogni si può costruire una a nastri con complessità - Se L è accettato da una MT A a
nastri con complessità , si può costruire una a 1 nastro (non a nastro singolo) con complessità = - Se
è accettato da una a nastri con complessità , per ogni si può costruire una a nastro con complessità - Se
è accettato da una a nastri con complessità , per ogni si può costruire una (a nastri) con complessità
Conseguenze:
-
Lo schema di dimostrazione è valido per qualsiasi tipo di modello di calcolo, quindi anche per calcolatori reali (es.: aumentare il parallelismo fisico (16bit → 32bit → . . . )).
-
Aumentando la potenza di calcolo in termini di risorse disponibili si può aumentare la velocità di esecuzione, ma il miglioramento è al più **lineare.
-
Miglioramenti di grandezza superiore al lineare possono essere ottenuti solo cambiando algoritmo e non in modo automatico.