Metodo di sostituzione per la risoluzione di una ricorrenza

[dlbp]

Ingegneria informatica

[fairyvilje]

Ok. Nel momento in cui si scrive un algoritmo può essere interessante stimare le sue prestazioni temporali o spaziali. Non è un qualcosa che si può fare per tutti gli algoritmi ma per la maggior parte di quelli che possono venirti in mente ci si riesce. Nel tuo caso il requisito è stimare la complessità temporale per una qualche funzione dell'input. Solitamente si considera la lunghezza dello stesso ma non è sempre così.
Ci sono due modi principali per rilevare le caratteristiche prestazionali: simulazione o analisi. La prima prevede l'esecuzione di un certo numero di istanze dell'algortimo, avendo cura di generare casi abbastanza vari da coprire la maggior parte delle possibilità, via via di "dimensione" crescente. Questo sistema va bene come fase conclusiva di un benchmark per verificare le caratteristiche "reali" di un algoritmo in un certo range e per ricavare i valori delle costanti che rientrano nell'analisi ibrida.
Tuttavia la stima più significativa va fatta in molti casi attraverso l'analisi (e in questo caso si parla proprio di dimostrazione). Ci sono vari modi per farla, l'analisi asintotica è solo uno dei tanti. L'idea è prendere il codice del proprio algoritmo e costruire il grafo equivalente. È una specie di diagramma di flusso dove si evidenzia il branching dato dalle condizioni nel codice, il "costo computazionale" delle istruzioni come peso degli archi, lo start e i vari ending-points. Se postassi il codice potrei farti un esempio direttamente su quello per come procedere.

[dlbp]

Guarda...ora non sono a casa e non ho il codice a portata di mano.

Comunque tornando alla notazione asintotica, devo cercare di stringere più possibile il limite superiore e inferiore o posso anche lasciarli laschi?

Grazie

[fairyvilje]

Ripeto per me stringere o allargare non ha nessun senso, stai dimostrando qualcosa di indimostrabile.