Dividir i vèncer

Capítols

1. 2.1
   L'esquema de dividir i vèncer

   Dividir, resoldre recursivament i combinar. Veuràs l'esquema general i com analitzar-ne el cost amb el teorema mestre.

   Llegit
2. 2.2
   Cerca binària

   Si el vector està ordenat, pots trobar un element en temps logarítmic descartant la meitat a cada pas.

   Llegit
3. 2.3
   Mergesort

   Ordenar dividint el vector per la meitat i fusionant les dues meitats ordenades. Cost garantit, però cal memòria auxiliar.

   Llegit
4. 2.4
   Quicksort

   Ordenar triant un pivot i partint el vector en menors i majors. Molt ràpid a la pràctica, encara que el cas pitjor és quadràtic.

   Llegit
5. 2.5
   Exponenciació ràpida i Karatsuba

   Dividir i vèncer també serveix per a aritmètica: elevar a una potència o multiplicar enters grans amb menys operacions.

   Llegit
6. 2.6
   Selecció i mediana

   Trobar l'element k-èsim sense ordenar tot el vector. Quickselect i el seu cost.

   Llegit
7. 2.7
   Consolidació

   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.

   Llegit