[Algoritmi e strutture dati] Analisi complessità

[fefy21]

Ciao a tutti. Sto preparando l'esame di algoritmi e strutture dati. Qualcuno mi saprebbe spiegare come calcolare, nel caso di algoritmi ricorsivi, la complessità temporale e spaziale nel caso migliore e nel caso peggiore?

[apatriarca]

Esistono interi corsi universitari e manuali che cercano di rispondere alla tua domanda. Un post su un forum è certamente non sufficiente per fornire una risposta sufficiente. In linea di massima ti scrivi l'equazione di ricorrenza e usi uno dei vari metodi esistenti per risolvere tale equazione. Se l'equazione di ricorrenza è risolvibile tramite il Teorema principale/Master theorem sei fortunatə. In caso contrario puoi più che altro basarti sull'esperienza su quale sia la strategia migliore (ci sono tecniche più avanzate e qualcuna abbastanza generica ma non credo facciano parte del tuo corso).

Il modo migliore per imparare è probabilmente provare a calcolare la complessità temporale e spaziale di diversi algoritmi.