Consolidació

• a) $\Theta(n \log n)$: $n$ accessos a un map, cadascun $\Theta(\log n)$ (la mida del map creix fins a $n$).
• b) $\Theta(n^2)$: inserir al principi d’un vector desplaça tots els elements que hi ha. Com que v ja en té $n$, cada inserció en desplaça entre $n$ i $2n - 1$: en total, $n + (n+1) + \dots + (2n-1) = \Theta(n^2)$.
• c) $\Theta(n)$: erase en una llista és $\Theta(1)$.
• d) $\Theta(n \log n)$: $n$ voltes amb un count i potser un [], tots dos $\Theta(\log n)$.

• a) $T(n) = 2T(n/2) + \Theta(1)$: divisió, $a = 2$, $b = 2$, $k = 0 < 1$: $\Theta(n)$.
• b) $T(n) = T(n/2) + \Theta(n)$: divisió, $a = 1$, $b = 2$, $k = 1 > 0$: $\Theta(n)$. (Escriu $n + n/2 + n/4 + \dots < 2n$ asteriscs.)
• c) $T(n) = T(n-1) + T(n-2) + T(n-3) + \Theta(1)$. Com a mínim és $3T(n-3)$, que ja és exponencial: $\Theta(c^n)$ per a una certa $c > 1$ (de fet, $c \approx 1{,}84$).

1. Totes les parelles:

int parelles_lent(const vector<int>& v, int k) {
    int compte = 0;
    for (int i = 0; i < int(v.size()); ++i)
        for (int j = i + 1; j < int(v.size()); ++j)
            if (v[i] + v[j] == k) ++compte;
    return compte;
}

$\Theta(n^2)$.

2. Un índex i al principi i un j al final. Mira $s = v[i] + v[j]$:

• si $s < k$, $v[i]$ és massa petit fins i tot amb el més gran que queda ($v[j]$): cap parella amb $v[i]$ funciona. Avança i.
• si $s > k$, $v[j]$ és massa gran fins i tot amb el més petit que queda: retrocedeix j.
• si $s = k$, n’hem trobat una. Com que els elements són diferents, ni $v[i]$ ni $v[j]$ poden formar cap altra parella: movem tots dos.

// Pre: v ordenat estrictament creixent.
// Post: retorna quantes parelles i < j tenen v[i] + v[j] = k.
int parelles(const vector<int>& v, int k) {
    int compte = 0;
    int i = 0, j = int(v.size()) - 1;
    // Inv: compte = parelles que fan k amb algun element fora de v[i..j];
    //      les parelles que queden són dins de v[i..j]
    while (i < j) {
        int s = v[i] + v[j];
        if (s == k) {
            ++compte;
            ++i;
            --j;
        }
        else if (s < k) ++i;
        else --j;
    }
    return compte;
}

Cada volta acosta i i j (fita: $j - i$): com a molt $n$ voltes, $\Theta(n)$.

Directa: a cada node, alcada(a.left()) > alcada(a.right()). Cada node és recorregut per alcada una vegada per cada avantpassat: $\Theta(n^2)$ en el cas pitjor (un arbre en línia).

Millorada, amb una immersió per resultats que retorna també l’alçada:

// Pre: cert. Post: retorna quants nodes de a tenen el fill esquerre més alt que el dret;
//      h és l'alçada de a.
int mes_alts_esquerra(const BinTree<int>& a, int& h) {
    if (a.empty()) {
        h = 0;
        return 0;
    }
    int he, hd;
    int n = mes_alts_esquerra(a.left(), he) + mes_alts_esquerra(a.right(), hd);
    h = 1 + max(he, hd);
    if (he > hd) ++n;
    return n;
}

$\Theta(n)$. És el mateix patró que l’arbre equilibrat: sempre que una funció sobre arbres necessiti una propietat dels subarbres que es calcula recursivament, fes que la recursió la retorni.

Directa: es porta el camí dels avantpassats en un vector, i a cada node es recorre sencer per veure si algun és més gran o igual.

// Pre: cami conté els valors dels avantpassats de a (de l'arrel al pare).
// Post: retorna quants nodes de a tenen un valor més gran que tots els seus avantpassats.
int records_arbre_lent(const BinTree<int>& a, vector<int>& cami) {
    if (a.empty()) return 0;
    bool record = true;
    for (int x : cami) if (x >= a.value()) record = false;   // Θ(profunditat)
    cami.push_back(a.value());
    int compte = records_arbre_lent(a.left(), cami) + records_arbre_lent(a.right(), cami);
    cami.pop_back();
    if (record) ++compte;
    return compte;
}

A cada node es fa una feina proporcional a la seva profunditat: $\Theta(n \cdot h)$, on $h$ és l’alçada. En una línia, $\Theta(n^2)$.

Millorada, amb una immersió per dades: en lloc de recalcular el màxim del camí, es passa cap avall.

// Pre: m és el màxim dels valors del camí des de l'arrel original fins al pare de a
//      (o INT_MIN, si a és l'arrel original). Cap valor de l'arbre és INT_MIN.
// Post: retorna quants nodes de a tenen un valor més gran que tots els seus avantpassats.
int records_arbre(const BinTree<int>& a, int m) {
    if (a.empty()) return 0;
    int nou = max(m, a.value());
    int compte = records_arbre(a.left(), nou) + records_arbre(a.right(), nou);
    if (a.value() > m) ++compte;
    return compte;
}

Crida inicial: records_arbre(a, INT_MIN) (cal <climits>). Cada node fa una feina constant: $\Theta(n)$. És el mateix patró que els rècords d’un vector: portar el màxim en lloc de recalcular-lo.

Amb $n$ operacions, l’estructura arriba a tenir $\Theta(n)$ elements.

1. Vector sense ordenar: afegir és $\Theta(1)$ (push_back); comptar els més petits és un recorregut, $\Theta(n)$. En el cas pitjor (meitat i meitat), $\Theta(n^2)$ en total.
2. Vector ordenat: comptar és una cerca dicotòmica ($\Theta(\log n)$: la posició del primer $\ge x$ és el nombre d’elements més petits). Però afegir és $\Theta(n)$ (cal desplaçar). Total $\Theta(n^2)$.
3. map: afegir és $\Theta(\log n)$, però per comptar els més petits cal recórrer el map fins a $x$: $\Theta(n)$ en el cas pitjor. Total $\Theta(n^2)$.

Cap de les tres no baixa de $\Theta(n^2)$ en el cas pitjor. Cal una estructura més sofisticada (un arbre de cerca on cada node sap la mida del seu subarbre, que veuràs a EDA) per fer totes dues operacions en $\Theta(\log n)$. De vegades la resposta a «quina estructura?» és «cap de les que tinc»: l’anàlisi de cost t’ho diu abans de programar res.