Analisi degli algoritmi¶
Parte 4 del corso, volume 4 delle dispense. L'analisi degli algoritmi: la dimensione dell'input, il tempo di esecuzione nel caso migliore, peggiore e medio, e la correttezza dimostrata con le invarianti di ciclo.
-
11. Dimensione dell'input
Dimensione dell'input · Notazione asintotica: un richiamo · Istanza di input costituita da un numero naturale · Istanza di input costituita da due numeri naturali · …
-
12. Tempo di esecuzione
Tempo di esecuzione di un algoritmo · Ricerca del massimo · Insertion sort · Cambio di base · …
-
13. Correttezza
Correttezza di un algoritmo · Correttezza di Find Maximum · Correttezza di Insertion Sort · Correttezza di Binary Search · …