EDA · Tema 1
Anàlisi d'algorismes
Com es mesura l'eficiència d'un algorisme sense dependre de l'ordinador. Notació asimptòtica, cas pitjor i mitjà, i recurrències.
Capítols
- 1.1Cost d'un algorismeLlegit
Comptar operacions en lloc de segons: així pots comparar algorismes en qualsevol màquina. Veuràs el cas millor, el pitjor i el mitjà.
- 1.2Anàlisi asimptòticaLlegit
Quan l'entrada és gran, només importa com creix el cost. Les notacions O, Ω i Θ et permeten dir-ho amb precisió.
- 1.3Cost dels algorismes iteratiusLlegit
Com calcular el cost d'un codi amb bucles: sumatoris, bucles niuats i regles per simplificar.
- 1.4Recurrències i teorema mestreLlegit
El cost d'un algorisme recursiu s'expressa amb una recurrència. Aprendràs a resoldre les més habituals, sobretot amb el teorema mestre.
- 1.5ConsolidacióLlegit
Repàs de tot el tema en una sola pàgina: les idees clau de cada capítol, com encaixen entre elles i els errors més habituals. Ideal per repassar abans de l'examen.