Algorismes: correcció, invariants de bucle i complexitat asimptòtica

Hi ha dues preguntes independents sobre qualsevol algorisme: fa el que ha de fer i quant costa. Es responen amb eines diferents i confondre-les és l'error conceptual d'aquest tema. Un algorisme ràpid i incorrecte no val res, i un de correcte però inviable tampoc.

Què vol dir que un algorisme és correcte

La correcció parcial diu que, si l'algorisme acaba i les precondicions es compleixen, la sortida satisfà la postcondició. La correcció total hi afegeix la terminació. Són dues coses separades i es demostren per separat.

L'eina per a la correcció parcial és l'invariant de bucle: una propietat que es compleix just abans d'entrar al bucle, es preserva a cada iteració, i que combinada amb la condició de sortida implica el que vols demostrar. Els tres passos són obligatoris; provar-ne només dos no demostra res.

L'eina per a la terminació és una variant: una quantitat entera no negativa que disminueix estrictament a cada iteració. Com que no pot baixar indefinidament, el bucle acaba.

Notació asimptòtica

Dir que $f(n) = O(g(n))$ significa que existeixen una constant $C > 0$ i un llindar a partir del qual $|f(n)|\leq C\,g(n)$. La notació $\Omega$ és la cota inferior anàloga i $\Theta$ vol dir les dues alhora.

Un bucle de $n$ passos amb cost constant és $\Theta(n)$. Però dos bucles niats no sempre donen $n^{2}$: cal mirar els límits reals. Si el bucle interior va fins a l'índex de l'exterior, el cost total és

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \Theta(n^{2}),$$

que sí que és quadràtic, però amb la meitat de la constant. I si el bucle interior fes un nombre constant de passos, el total seria lineal.

Per a les recursions, l'ordenació per fusió satisfà $T(n) = 2T(n/2) + \Theta(n)$, que dona $\Theta(n\log n)$. La lectura és directa: hi ha $\log_2 n$ nivells de recursió i a cada nivell es fa un treball total lineal.

Un avís pràctic sovint oblidat: l'aritmètica amb enters grans no té cost constant. Quan la longitud dels operands creix amb l'entrada, cal distingir el nombre d'operacions de la complexitat en bits.

Algorismes de grafs

Amb llistes d'adjacència, les cerques en amplada i en profunditat costen $O(|V|+|E|)$: cada vèrtex i cada aresta es visiten un nombre constant de vegades. La cerca per amplada dona a més les distàncies mínimes en nombre d'arestes en grafs no ponderats, perquè explora per capes.

Dijkstra calcula distàncies mínimes amb pesos no negatius. A cada pas fixa definitivament el vèrtex provisional de distància mínima. La justificació és exactament la no-negativitat: qualsevol camí alternatiu hauria de passar per un vèrtex encara no fixat, que ja té distància provisional més gran, i afegir-hi arestes no negatives no pot millorar-la. Amb un munt binari, el cost habitual és $O((|V|+|E|)\log|V|)$.

Per a l'arbre d'expansió mínim d'un graf connex no dirigit, Kruskal ordena les arestes per pes i va afegint les que no tanquen cap cicle. La justificació correcta és la propietat del tall: donada qualsevol partició dels vèrtexs en dos grups, una aresta de pes mínim que els travessi es pot incloure en algun arbre òptim. Dir només «sempre agafem la més barata» no és una demostració: és una descripció, i hi ha problemes on aquesta estratègia voraç falla.

Exercici resolt: cost d'un bucle de duplicació

Un bucle comença amb $x = 1$ i repeteix $x \leftarrow 2x$ fins que $x \geq n$. Quantes iteracions fa?

Després de $k$ passos, $x = 2^{k}$. La condició de sortida és $2^{k}\geq n$, és a dir

$$k \geq \log_2 n, \qquad k = \lceil \log_2 n\rceil.$$

El cost és $O(\log n)$ en el model d'operacions unitàries.

El matís que gairebé sempre s'oblida. Si $n$ és astronòmic, el número $x$ té fins a $\log_2 n$ bits i cada duplicació ja no és una operació de cost constant. En complexitat de bits el cost puja. Per a mides de màquina habituals el model unitari és raonable, però cal dir-ho.

Exercici resolt: invariant d'una suma acumulada

Un bucle recorre una llista i va acumulant en una variable $s$, començant amb $s = 0$. Quin és l'invariant i què demostra?

Invariant: després de processar els $i$ primers elements, $s$ val exactament la suma d'aquests $i$ elements.

Inicialització: amb $i = 0$, la suma de cap element és $0$, i $s = 0$. Es compleix.

Preservació: si es compleix per a $i$ i el pas següent fa $s \leftarrow s + a_{i+1}$, aleshores la nova $s$ és la suma dels $i+1$ primers. Es preserva.

Terminació: el bucle acaba amb $i = n$, i combinat amb l'invariant això diu que $s$ és la suma de tots els elements, que és exactament la postcondició.

Variant: la quantitat $n - i$, entera, no negativa i estrictament decreixent. Demostra terminació, i el cost és $\Theta(n)$.

Aquest esquema de quatre passos (inicialització, preservació, terminació, variant) és el que s'espera en qualsevol demostració de correcció, i es pot escriure sempre igual.