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 [latex]\vartheta[/latex], el seu cost (eficiència) és una funció: [latex]\begin{array}{ll}T: & \vartheta \rightarrow \mathbb{R}^{+} \\ & \alpha \mapsto T(\alpha)\end{array}[/latex]

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

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:

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

Observacions:

  • [latex]T_{millor}(n) \le T_{n}(\alpha) \le T_{pitjor}(n)[/latex]
  • [latex]T_{millor}(n) \le T_{mitj\grave{a}}(n) \le T_{pitjor}(n)[/latex]

Notació asimptòtica

Considerem funcions del tipus [latex]f: \mathbb{N} \rightarrow \mathbb{N}[/latex]. Definim:

  • [latex]O(f) = \left\{g: \mathbb{N} \rightarrow \mathbb{N}, \exists n_0 \ge 0, \forall n \ge n_{0}: g(n) \le f(n) \cdot c_{0}\right\}[/latex] [latex]g \in O(f) \Leftrightarrow[/latex] «[latex]g[/latex] creix més a poc a poc o igual que [latex]f[/latex]» (per a valors prou grans i ignorant les pendents)
  • [latex]\Omega(f) = \left\{g: \mathbb{N} \rightarrow \mathbb{N}, \exists n_0 \ge 0, \forall n \ge n_{0}: g(n) \ge f(n) \cdot c_{0}\right\}[/latex] [latex]g \in \Omega(f) \Leftrightarrow[/latex] «[latex]g[/latex] creix més ràpid o igual que [latex]f[/latex]»
  • [latex]\theta(f) = O(f) \cap \Omega(f)[/latex] [latex]g \in \Omega(f) \Leftrightarrow[/latex] «[latex]g[/latex] creix igual que [latex]f[/latex]» (en altres paraules, [latex]g[/latex] i [latex]f[/latex] tenen el mateix ordre de creixement)

Considerant [latex]g: \mathbb{N} \rightarrow \mathbb{R}^{+}[/latex] les definicions serien similars.

Propietats

    • [latex]\lim_{n \to \infty} \frac{f(n)}{g(n)} \lt +\infty \Rightarrow f \in O(g)[/latex]
    • [latex]\lim_{n \to 0} \frac{f(n)}{g(n)} \gt 0 \Rightarrow f \in \Omega(g)[/latex]
    • [latex]\lim_{n \to \infty} \frac{f(n)}{g(n)} \in (0, \infty) \Rightarrow f \in \theta(g)[/latex]
    • Nota: Regla de L'Hôpital.
  • Reflexivitat: [latex]f \in O(f)[/latex] (ídem per a [latex]\Omega[/latex] i [latex]\theta[/latex])
  • Transitivitat: [latex]f \in O(g) \land g \in O(h) \Rightarrow f \in O(h)[/latex] (semblant per a [latex]\Omega[/latex] i [latex]\theta[/latex])
  • Regles de càlcul:
    • [latex]O(f) = O(f \cdot c) \forall c \gt 0 ct.[/latex]
    • [latex]O(f) + O(g) = O(f + g) = O\left(m\grave{a}x\{f, g\}\right)[/latex]
    • [latex]O(f) \cdot O(g) = O(f \cdot g)[/latex]
    • (ídem per a [latex]\Omega[/latex] i [latex]\theta[/latex])

Convenció

Per convenció es fa un abús del llenguatge i sovint escrivim [latex]f = O(g)[/latex] quan realment volem dir [latex]f \in O(g)[/latex]. (Cal tenir en compte això a l'utilitzar la propietat de transitivitat!) Per exemple:

  • [latex]4n = O(n^2) = O(n^3)[/latex] on realment hauria de ser [latex]\subseteq[/latex]
  • [latex]2n = O(n)[/latex]

Funcions de cost

En general, tenim un algorisme [latex]A[/latex] amb un conjunt d'entrades [latex]E[/latex]. Volem caracteritzar l'ús d'algun recurs quan s'executa [latex]A[/latex] sobre una entrada [latex]x \in E[/latex].

[latex]\begin{array}{ll}C_{A}: & E \rightarrow \mathbb{N} \\ & x \mapsto C_{A}(x)\end{array}[/latex]

Obtenir [latex]C_{A}(x)[/latex] és, en general, massa difícil [latex]\Rightarrow[/latex] simplifiquem. No mirem cada entrada individual sinó que ajuntem totes les entrades de la mateixa talla. Anomenem [latex]|x|[/latex] la talla d'[latex]x[/latex].

Estudiem els algorismes calculant el seu cost en funció de la talla de les seves entrades. A més, només mirarem els costos pitjor i millor (veure introducció) i [latex]C_{mitj\grave{a}}(n) = \frac{1}{|E_{n}|} \sum_{x \in E_{n}} C_{A}(x)[/latex] on [latex]E_{n} = \left\{x \in E \mid |x|= n\right\}[/latex] (aquesta darrera funció de cost és difícil d'obtenir i no té en compte les probabilitats).

[latex]\forall x \in E: c_{millor}(|x|) \le C_{A}(x) \le C_{pitjor}(|x|)[/latex]

[latex]\forall n: c_{millor}(n) \le C_{mitj\grave{a}}(n) \le C_{pitjor}(n)[/latex]

Així doncs, en algorísmica calculem els costos dels algorismes donant fites (superiors i inferiors) en funció de la talla de les entrades, utilitzant notació asimptòtica.

Cost d'algorismes recursius

El cost dels algorismes recursius s'expressa generalment mitjançant una equació recorrent (recurrència). El cost de l'algorisme ve donat per la solució a aquesta. Dos tipus de recurrències freqüents són les recurrències substractores i les recurrències divisores.

Recurrències substractores

Les recurrències substractores prenen la forma següent:

[latex]T(n) = \begin{cases}f(n) & n \le k' \\ a \cdot T(n – c) + g(n) & n > k' \end{cases}[/latex]

On [latex]a[/latex] és una constant no negativa ([latex]a \ge 0[/latex]), [latex]c[/latex] és una constant estrictament positiva ([latex]c \ [/latex]) i [latex]g[/latex] és una funció amb cost [latex]\theta(n^k)[/latex].

Teorema mestre I (per a recurrències substractores)

Donada la recurrència anterior, trobem el cost segons: [latex]T(n) = \begin{cases}\theta(n^k) & a < 1 \\ \theta(n^{k+1}) & a = 1 \\ \theta(a^{n/c}) & a > 1\end{cases}[/latex]

Recurrències divisores

Les recurrències divisores prenen la següent forma:

[latex]T(n) = \begin{cases}f(n) & n \le c' \\ a \cdot T(\frac{n}{b}) + g(n) & n > c' \end{cases}[/latex]

On [latex]a[/latex] és una constant no negativa ([latex]a \ge 0[/latex]), [latex]b > 1[/latex] i [latex]g[/latex] és una funció amb cost [latex]\theta(n^k)[/latex].

Teorema mestre II (per a recurrències divisores)

Sigui [latex]\alpha = log_{b}(a)[/latex], i donada la recurrència anterior, aleshores: [latex]T(n) = \begin{cases}\theta(n^k) & \alpha < k \\ \theta(n^{\alpha} \cdot log n) & \alpha = k \\ \theta(n^{\alpha}) & \alpha > k\end{cases}[/latex]