Introducció

L'esquema de programació de dividir i vèncer és una tècnica per a resoldre problemes que consisteix en dividir el problema original en subproblemes (més petits), resoldre els subproblemes i finalment combinar les solucions en una sola que resolgui el problema original. Mitjançant aquest tècnica sovint obtenim una solució recursiva.

Exemples

1. Cerca dicotòmica: \(T(n) = O(log n)\)
2. Exponenciació ràpida: \(T(n) = \theta(log n)\)
   \(x^n = \begin{cases}1 & n = 0 \\ (x^2)^{\frac{n}{2}} & n \gt 0, n\ \acute{e}s\ parell \\ x \cdot (x^2)^{\left\lfloor \frac{n}{2} \right\rfloor} & n \gt 0, n\ \acute{e}s\ senar\end{cases}\)
3. Merge sort: \(T(n) = \theta(n log n)\)
4. Quick sort (inventat el 1960 per Hoare): \(T(n) = \begin{cases}\small cas\ millor: & 2T(\frac{n}{2}) + \theta(n) & \rightarrow \theta(n log n) \\ \small cas\ mitj\grave{a}: & \frac{1}{n}\sum_{i=1}^{n}T(i) + T(n-i) + \theta(n) & \Rightarrow \theta(n log n) \\ \small cas\ pitjor: & c + T(n – 1) + \theta(n) & \Rightarrow \theta(n^2)\end{cases}\)

   Consististeix en agafar un pivot \(x\) i dividir l'entrada en aquells elements \(\le x\) i aquells \(\ge x\), i repetir aquest procediment de forma recursiva en els dos grups. En la definició de \(T(n)\), \(i\) representa el nombre d'elements \(\le x\) i depèn del pivot.

   

   Nota: La llibreria estàndard de C++ disposa d'una implementació de l'algorisme Introsort, que ordena amb quick sort però compta el nombre de crides recursives. A partir d'un cert nombre \(c_{2} \cdot log n\) canvia a heap sort.

5. Quick Select (selecció del \(k\)-èssim element d'una taula desordenada) \(T(n) = \begin{cases}\small cas\ millor\ i\ mitj\grave{a}: & s(n) = s(\frac{n}{2}) + \theta(n) & \Rightarrow \theta(n) \\ \small cas\ pitjor: & s(n) = s(n – 1) + \theta(n) & \Rightarrow \theta(n^2)\end{cases}\)

   Consisteix en agafar un pivot \(x\), fer la partició i trobar la posició \(q\) de l'element de més a la dreta del primer grup. Si \(q = k\) llavors ja hem acabat (el \(k\)-èssim és l'element \(T[q]\)); si \(q \lt k\) cerquem l'element \(k – q\) al segon grup; finalment, si \(q \gt k\), cerquem l'element \(k\)-èssim a T1.

   Nota: existeix un altre algorisme de selecció en temps lineal en el cas pitjor: Floyd-Wilson.

6. Algorisme de Karasuba (per a multiplicar)

   L'algorisme per a multiplicar clàssic du a terme \(O(n^2)\) operacions. L'algorisme de Karatsuba és més ràpid per a nombres molt grans.

   Sense pèrdua de generalitat: suposem nombres binaris, de la mateixa longitud i sent aquesta longitud una potència de 2. Per exemple, x = [a|b], y = [c|d].
   \((a \cdot 2^{\frac{n}{2}} + b) (c \cdot 2^{\frac{n}{2}} + d) = x \cdot y\)
   \(u = (a+b) (c+d)\ \ \ \ v = a \cdot c\ \ \ \ w = b \cdot d\)
   \(x \cdot y = v \cdot 2^n + (u – v – w) \cdot 2^(\frac{n}{2}) + w\)

   \(T(n) = 3T(\frac{n}{2}) + \theta(n) \Rightarrow T(n) = \theta(n^{log_{2}3 \simeq 1.585})\)

Alguns apunts addicionals:

• El merge sort (implementat correctament) és un algorisme d'ordenació estable, amb el quick sort aquest no és el cas.
• L'algorisme quick sort cau en el seu temps pitjor quan l'entrada ja està ordenada.

Implementació del quick sort

int partició<vector<elem>& v, int e, int d) {
    // Hoare
    Elem x = v[e];
    int i = e - 1;
    int j = d + 1;
    while (true) {
        while (v[--j] > x);
        while (v[++i] < x);
        if (i >= j) return j;
        swap (v[i], v[j]);
    }
}
void quicksort(vector<elem>& v, int e, int d) {
    if (e < d) {
        int p = partició(v, e, d);
        quicksort(v, e, p);
        quicksort(v, p+1, e);
    }
}

Enllaços rellevants

• Esquema de Dividir y Vencer, Amalia Duch.
• Merge sort i Quick sort, Wikipedia.
• Explicació i exemple interactiu del QuickSelect.

Introducció L'esquema de programació de dividir i vèncer és una tècnica per a resoldre problemes que consisteix en dividir el problema original en subproblemes (més petits), resoldre els subproblemes i finalment combinar les solucions en una sola que resolgui el problema original. Mitjançant aquest tècnica sovint obtenim una solució recursiva. Exemples Cerca dicotòmica: Exponenciació ràpida: Merge sort: ...

Introducció

Els algorismes són per tot arreu i per això volem analitzar-ne les característiques. Algunes de les característiques més importants dels algorismes són:

• correctesa!
• senzillesa
• escalabilitat
• modularitat
• eficiència
• fiabilitat
• etc.

Nosaltres en concret en mirarem l'eficiència i l'ús dels recursos del sistema a nivell teòric, és a dir, el temps d'execució, la quantitat de memòria que utilitzen, etc.

Suposarem que el cost de totes les operacions elementals és constant, i anomenem «n» la mida de l'entrada, en funció de la qual veurem el cost en temps i memòria dels algorismes.

Def. Donat un algorisme A, amb conjunt d'entrades \(\vartheta\), el seu cost (eficiència) és una funció: \(\begin{array}{ll}T: & \vartheta \rightarrow \mathbb{R}^{+} \\ & \alpha \mapsto T(\alpha)\end{array}\)

Per facilitar la manipulació de cost restringim el conjunt \(\vartheta\) al conjunt \(\vartheta_{n}\), que correspon al de totes les entrades de mida \(n \in \mathbb{R}\).

Def. Donat un algorisme A, amb un conjunt d'entrades de mida n (\(\vartheta_{n}\)), el cost d'A en el cas millor, pijtor i mitjà és:

• \(T_{millor}(n) = min\left\{T_{n}(\alpha) | \alpha \in \vartheta_{n}\right\}\)
• \(T_{pitjor}(n) = max\left\{T_{n}(\alpha) | \alpha \in \vartheta_{n}\right\}\)
• \(T_{mitj\grave{a}}(n) = \sum_{\alpha \in \vartheta_{n}} Pr(\alpha) \cdot T_{n}(\alpha)\)
  (suposant un coneixement de la distribució estadística de les entrades)

Observacions:

• \(T_{millor}(n) \le T_{n}(\alpha) \le T_{pitjor}(n)\)
• \(T_{millor}(n) \le T_{mitj\grave{a}}(n) \le T_{pitjor}(n)\)

Continue reading →

Introducció Els algorismes són per tot arreu i per això volem analitzar-ne les característiques. Algunes de les característiques més importants dels algorismes són: correctesa! senzillesa escalabilitat modularitat eficiència fiabilitat etc. Nosaltres en concret en mirarem l'eficiència i l'ús dels recursos del sistema a nivell teòric, és a dir, el temps d'execució, la quantitat de memòria que utilitzen, etc. Suposarem que el cost de totes ...