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: [latex]T(n) = O(log n)[/latex]
  2. Exponenciació ràpida: [latex]T(n) = \theta(log n)[/latex]
    [latex]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}[/latex]
  3. Merge sort: [latex]T(n) = \theta(n log n)[/latex]
  4. Quick sort (inventat el 1960 per Hoare): [latex]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}[/latex]

    Consististeix en agafar un pivot [latex]x[/latex] i dividir l'entrada en aquells elements [latex]\le x[/latex] i aquells [latex]\ge x[/latex], i repetir aquest procediment de forma recursiva en els dos grups. En la definició de [latex]T(n)[/latex], [latex]i[/latex] representa el nombre d'elements [latex]\le x[/latex] 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 [latex]c_{2} \cdot log n[/latex] canvia a heap sort.

  5. Quick Select (selecció del [latex]k[/latex]-èssim element d'una taula desordenada)

    [latex]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}[/latex]

    Consisteix en agafar un pivot [latex]x[/latex], fer la partició i trobar la posició [latex]q[/latex] de l'element de més a la dreta del primer grup. Si [latex]q = k[/latex] llavors ja hem acabat (el [latex]k[/latex]-èssim és l'element [latex]T[q][/latex]); si [latex]q \lt k[/latex] cerquem l'element [latex]k – q[/latex] al segon grup; finalment, si [latex]q \gt k[/latex], cerquem l'element [latex]k[/latex]-è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 [latex]O(n^2)[/latex] 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].
    [latex](a \cdot 2^{\frac{n}{2}} + b) (c \cdot 2^{\frac{n}{2}} + d) = x \cdot y[/latex]
    [latex]u = (a+b) (c+d)\ \ \ \ v = a \cdot c\ \ \ \ w = b \cdot d[/latex]
    [latex]x \cdot y = v \cdot 2^n + (u – v – w) \cdot 2^(\frac{n}{2}) + w[/latex]

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

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