Iterazione Questo metodo semplicemente consiste di calcolare tutte le operazioni e scriverlo con una notazione asintotica. slide Sostituzione (induzione) slide Analisi della relazione di ricorrenza di fibonacci Si pu貌 dimostrare utilizzando l鈥檌nduzione che una relazione di questo tipo $$ T(n) = \begin{cases} O(1) \\ T(n-1) + T(n-2) + 1 \end{cases} $$Si trova che 猫 $O(2^n), \Omega(2^{n/2})$ Analisi finale. ...
3.1 Introduzione 3.1.1 Cosa sono Le strutture di dati si interessano solamente di come memorizzare i dati, non necessariamente va a memorizzare un tipo di dato concreto. Quindi + sul come - sul cosa. 3.1.2 Prototipo e implementazione Avevamo introdotto la differenza fra algoritmo e programma all鈥檌nizio del corso, andiamo ora a definire la differenza fra prototipo e implementazione: Prototipo: va a fare una descrizione dei metodi che deve avere una determinata struttura di dati. Lo puoi intendere come una specie di interfaccia. ...
Alberi BST e AVL 4.1 Alberi binari di ricerca (BST) Queste sono delle varianti rispetto all鈥檃lbero, descritto in modo molto sommario sopra (binario perch茅 ogni nodo ha al massimo due figli, mentre l鈥檃lbero pu貌 averne quanti se ne vuole). 4.1.1 Introduzione La caratteristica principale dell鈥檃lbero di ricerca 猫 una condizione sulle chiavi (che hanno i figli). Infatti questo albero binario di ricerca si pu貌 vedere come una implementazione della struttura astratta del dizionario. (che ricordiamo, 猫 un struttura in cui a ogni nodo sono presenti due valori, una chiave (tute differenti) e un dato, e sono definite tre operazioni principali, possiamo vederla come interfaccia). ...