Projets : complexités de problèmes algorithmiques

On donne trois preuves possibles.

En reprenant la définition

Si la première condition ($i=0$) est vérifiée, le tableau contient un col. On la suppose donc non vérifiée : $T[0] > T[1]$. De même, si la seconde condition ($i=n-1$) est vérifiée, le tableau contient également un col. Supposons la donc également non vérifiée : $T[n-2] < T[n-1]$.

Les deux conditions précédentes montrent qu'il existe $n-1 > i^\star > 0$ le plus petit indice tel que $T[i^\star] \leq T[i^\star +1]$. On a alors : $T[i^\star -1] > T[i^\star ] \leq T[i^\star +1]$ et $i^\star$ est un col.

On utilise une astuce

Un tableau d'entier possède forcément un élément minimum. Il existe donc $i^\star$ tel que $T[i^\star] \leq T[i]$ pour tout $0 \leq i < n$. De là :

• soit $i^\star = 0$ et $T[i^\star] \leq T[1]$
• soit $i^\star = n-1$ et $T[i^\star] \leq T[n-2]$
• soit $0 < i^\star < n-1$ et $T[i^\star] \leq \min(T[i^\star-1], T[i^\star+1])$

Simple et efficace, non ?

Par récurrence

On montre par récurrence sur la taille $n$ du tableau qu'il existe toujours un col.

1. Initialisation. Si $n=2$ soit $T[0] \leq T[1]$ soit $T[0] \geq T[1]$ (ce qui est équivalent pour $n=2$ à $T[n-1] \leq T[n-2]$). Ces deux cas correspondent aux deux premières possibilités pour un col
2. on suppose la propriété vrai pour $n \geq 2$. Et on se donne un tableau $T$ de taille $n+1$.
3. l'hypothèse de récurrence stipule que le tableau $T'$ constitué des $n$ premières cases de $T$ ($T'= T[:-1]$) possède un col, disons à l'indice $i^\star$. 3 cas sont possibles :
   1. $i^\star = 0$ et $T'[0] \leq T'[1]$ ce qui implique $T[0] \leq T[1]$ : $i^\star$ est aussi un col pour $T$
   2. $0 < i^\star < n-1$ et $T'[i^\star] \leq \min(T'[i-1], T'[i+1])$ ce qui implique $T[i^\star] \leq \min(T[i^\star-1], T[i^\star+1])$ : $i^\star$ est aussi un col pour $T$
   3. $i^\star = n-1$ et $T'[n-1] \leq T'[n-2]$ ce qui implique $T[n-1] \leq T[n-2]$. On conclut en remarquant que :
      1. soit $T[n] \geq T[n-1]$ et $T[i^\star] \leq \min(T[i^\star-1], T[i^\star+1])$ : $i^\star$ est aussi un col pour $T$
      2. soit $T[n] < T[n-1]$ et $n$ est un col pour $T$.

La preuve de la 1ère question montrant qu'il existe forcément un col, l'algorithme suivant qui mime directement la définition (lignes 2-3 : 1ère condition, lignes 5-6 : 2ème condition et lignes 8-10 la troisième condition) trouvera forcément un col :

algorithme trouve(T: [entier]) → entier:  # T.longueur > 1
    si T[0] ≤ T[1]:
        rend 0

    si T[-1] ≤ T[-2]:
        rendre T.longueur - 1

    pour chaque (i := entier) de [1 .. T.longueur - 1[:
        si T[i] ≤ min(T[i-1], T[i + 1]):
            rendre i

Sa complexité dans le cas le pire a lieu pour les tableaux dont le premier et seul col se trouve à l'avant dernier indice (comme pour la liste $[5, 4, 3, 2, 1, 2]$ par exemple), forçant l'algorithme à :

• faire échouer le 1er test de la ligne 2 en $\mathcal{O}(1)$ opérations
• faire échouer le 2er test de la ligne 5 en $\mathcal{O}(1)$ opérations
• faire les $\mathcal{O}(n)$ itérations de la boucle for en :
  • faisant échouer tous les tests sauf le dernier $\mathcal{O}(1)$ opérations
  • réussissant le dernier test et en faisant un retour de fonction en $\mathcal{O}(1)$ opérations

La complexité totale maximale est alors :

$$ C(n) = \mathcal{O}(1) + \mathcal{O}(1) + \mathcal{O}(n) \cdot (\mathcal{O}(1) + \mathcal{O}(1)) = \mathcal{O}(n) $$

On peut aussi utiliser la preuve précédente et simplifier la boucle pour chaque en gardant la même complexité :

algorithme trouve(T: [entier]) → entier:  # T.longueur > 1
    si T[0] ≤ T[1]:
        rend 0

    si T[-1] ≤ T[-2]:
        rendre T.longueur - 1

    pour chaque (i := entier) de [1 .. T.longueur - 1[:
        si T[i] ≤ T[i + 1]:
            rendre i

def trouve_vite(T):
    if T[0] <= T[1]:
        return 0

    if T[-1] <= T[-2]:
        return len(T) - 1

    début = 0
    fin = len(T) - 1

    while True:
        milieu = (fin + début) // 2
        if T[milieu] <= min(T[milieu - 1], T[milieu + 1]):
            return milieu

        if T[milieu] > T[milieu - 1]:
            fin = milieu
        else:
            début = milieu

La preuve d'existence du 1 montre que pour tout $i + 1 < j$, si $T[i] > T[i+1]$ et $T[j] > T[j-1]$, alors il existe un indice $i < k < j$ tel que $k$ soit un col de la matrice.

L'invariant de boucle de la boucle tant que est alors :

Invariant de boucle : A la fin de chaque itération de la boucle tant que, soit :

• T[milieu] est un col
• T[milieu] n'est pas un col et :
• début + 1 < fin
• T[début] > T[début+1] et T[fin] > T[fin-1]

A la fin de la première itération, on a soit :

• T[milieu] <= min(T[milieu - 1], T[milieu + 1]) et milieu est un col
• fin' = milieu et début' = début si T[milieu] > T[milieu -1]. Comme initialement 0 = début + 1 < fin = len(T) - 1 on a également milieu - 1 > début puisque T[0] > T[1] et l'invariant est vérifié.
• fin' = fin et début' = milieu si T[milieu] <= T[milieu -1] et T[milieu] > T[milieu + 1]. Comme 0 = début + 1 < fin = len(T) - 1 on a également milieu + 1 < fin puisque T[-1] > T[-2] et l'invariant est vérifié.

La même démonstration fonctionne à l'identique à la fin de l'itération $i+1$ si l'invariant est vrai à la fin de l'itération $i$.

Comme fin - début >= 0 et diminue strictement à chaque itération de la boucle tant que, il arrivera forcément un moment où milieu sera un col.

La procédure de la boucle tant que est identique à la recherche dichotomique puisque l'on se place toujours au milieu de l'espace de recherche. Le cours nous indiquant que la complexité de la recherche dichotomique est $\mathcal{O}(\log_2(n)) = \mathcal{O}(\ln(n))$, on en conclut que l'algorithme trouve_vite(T) est également en $\mathcal{O}(\ln(n))$ opérations.

Il existe des tableaux ayant tous un unique col en position $i$ pour tout $0 \leq i < n$ (prenez les tableaux $[0, -1, \dots, -i, -i+1, -i +2, \dots, -i + (n - i - 1)]$). Tout algorithme trouvant les col des tableaux doit donc pouvoir distinguer parmi $n$ cas : il est au moins de complexité $\mathcal{O}(\log_2(n)) = \mathcal{O}(\ln(n))$.

Comme l'algorithme trouve_vite(T) est de complexité $\mathcal{O}(\ln(n))$, c'est borne min est atteinte.

On suppose que l'on a les trois emplacements de tours A, B et C ; et que l'on veuille déplacer les disques de la tour A vers la tour C.

1. pour pouvoir déplacer le plus grand disque de la tour A, il faut avoir déplacé tous les disques au-dessus de lui. Comme c'est le plus grand disque, il est de plus seul sur son emplacement
2. une fois le plus grand disque seul sur sa tour, il faut le déplacer en C (ce disque peut être en B ou en A)
3. une fois le plus grand disque à sa place, il convient de déplacer la tour formée des autres disques sur l'emplacement C.

On a donc l'algorithme suivant :

fonction déplace(départ: [entier], arrivée: [entier]):
    (disque := entier) ← départ[départ[0]]
    départ[0] ← départ[0] - 1 
    arrivée[0] ← arrivée[0] + 1 
    arrivée[arrivée[0]] ← disque

algorithme Hanoï(nombre: entier, départ: [entier], arrivée: [entier], intermédiaire: [entier]):
    si nombre > 0:
        Hanoï(nombre - 1, départ, intermédiaire, arrivée)  # déplace n-1 à intermédiaire
        déplace(départ, arrivée)                           # place le premier disque
        Hanoï(nombre - 1, intermédiaire, arrivée, départ)  # déplace n-1 de intermédiaire à arrivée

Comme les tableau sont mutables, les objets sont déplacés dans le tableau on a besoin de ne rien rendre.

Si $N(n)$ est le nombre de récursions. déplacements pour résoudre le problème de la tour de Hanoï, il faut donc au moins :

1. déplacer une tour de $n-1$ éléments : $1 + N(n-1)$ récursions
2. re-déplacer une tour de $n-1$ éléments : $1 + N(n-1)$ récursions

On a donc un nombre de récursion de :

On obtient facilement l'expression, pour $n\geq 1$ :

Comme, hors récursion, l'algorithme effectue $\Theta(1)$ opérations, la complexité $C(n)$ de l'algorithme vaut $C(n) = \Theta(1) \cdot N(n) + \Theta(1)$ (le dernier $\mathcal{O}(1)$ vient du fait que pour $n =0$ il n'y a pas de récursion mais tout de même $\Theta(1)$ opérations).

On a donc au final une complexité valant :

On a utilisé des listes qui permettent d'ajouter ou de supprimer des éléments. Cela ne change pas la complexité (on le justifiera plus tard, lorsque l'on étudiera les structures de listes)

A = list(range(5, 0, -1))
B = []
C = []

def déplace(départ, arrivée):
    disque = départ.pop()
    arrivée.append(disque)

def Hanoi(n, départ, arrivée, intermédiaire):
    if n == 0:
        return
    Hanoi(n-1, départ, intermédiaire, arrivée)
    déplace(départ, arrivée)
    print(A, B, C)
    Hanoi(n-1, intermédiaire, arrivée, départ)

print(A, B, C)
Hanoi(len(A), A, C, B)

Si $D(n)$ est le nombre de déplacements pour résoudre le problème de la tour de Hanoï, il faut donc au moins :

1. déplacer une tour de $n-1$ éléments pour pouvoir déplacer le dernier disque : nombre de déplacement $D(n-1)$
2. déplacer le dernier disque
3. re-déplacer une tour de $n-1$ éléments sur le dernier disque : nombre de déplacement $D(n-1)$

On a donc l'inégalité : $D(n) \leq 1 + 2 \cdot D(n-1)$ pour tout algorithme de déplacement. Comme on a l'égalité pour notre algorithme, il est optimal.

Le nombre minimal de déplacement est :

On obtient facilement l'expression, pour $n\geq 1$ :

Le lecteur averti se sera rendu compte que c'est exactement notre complexité.

• $\lambda = 7$
• $\mu = 3$

De part la définition la suite a $\lambda + \mu -1 $ valeurs distinctes de $a_0$ à $a_{ \mu + \lambda -1}$. La somme $\lambda + \mu$ est donc unique. De plus, tous les $m$ tels que $a_{ \mu + m} = a_{ \mu }$, sont multiples d'une valeur qui est l'unique $\lambda$ possible (pour garantir l'unicité des $\lambda + \mu -1 $ premières valeurs de la suite).

Il faut forcément parcourir les $\lambda + \mu -1$ premiers éléments de la suite pour garantir qu'ils sont tous différents et s'assurer que $a_{ \mu + \lambda} = a_{ \mu }$

Si la suite est ultimement périodique, il existe $j < i$ tel que $a(i) == a(j)$. Ceci prouve :

• la finitude de notre algorithme
• son exactitude : puisque pour tout $i>0$ on teste tous les $j < i$

L'algorithme va s'arrêter au plus petit $i$ tel qu'il existe $j < i$ tel que $a(i) == a(j)$ : $i = \lambda + \mu$ et $j = \mu$. Comme on à essayés tous couples plus petit la complexité est :

À chaque étape l'écart entre le lièvre et la tortue est augmenté de 1. Une fois la tortue et le lièvre sur le cycle il va forcément arriver un moment où le lièvre va prendre un tour à la tortue, et ceci va arriver avant que la tortue n'ait fait un tour de cycle complet.

Formalisons ça. Lorsque $m = \mu$, on a $a_{2\mu} = a_{\mu + k} = a_{m + k}$ avec $0 \leq k \leq \lambda$ puisque l'on se trouve sur le cycle de longueur $\lambda$.

Si $k=0$ ou $k=\lambda$ on a bien trouvé notre $m$ et sinon, comme $a_{2(\mu + p)} = a_{2\mu + 2p} = a_{\mu + 2p + k} = a_{(\mu + p) + p + k}$ en prenant $0 < p = \lambda - k < \lambda$ on a bien $a_{2(\mu + p)} = a_{(\mu + p) + \lambda} = a_{(\mu + p)}$ ce qui conclut la preuve.

À la fin de chaque étape le lièvre vaut 2 fois la tortue et s'arrête au premier élément ou il y a égalité. O sait que c'est élément est entre $\mu$ et $\lambda + \mu$.

Comme la valeur de la tortue est inférieure à $\lambda + \mu$, il n'y a eu au pire que $\lambda + \mu$ itérations d'une boucle en $\mathcal{O}(1)$.

Puisque $m\geq \mu$ on est sur le cycle de longueur $\lambda$. Donc pour que $a_{m} = a_{2m}$ il faut que $2m = m + k\lambda$ ce qui montre que $m$ est un multiple de $\lambda$.

La division entière de $\mu$ par $\lambda$ donne $\mu = b + k \cdot \lambda$ avec $b < lambda$. Comme de plus $\mu \leq m \leq \mu + \lambda$, on a $b + k \cdot \lambda \leq m \leq b + (k + 1) \cdot \lambda$.

Or $m$ est un multiple de $k$, on ne peut donc avoir que $m = (k+1) \cdot \lambda$. En injectant cette égalité dans $\mu$ on obtient : $\mu = b + k \cdot \lambda = b + (m - \lambda)$ ce qui conclut la preuve.

La question précédente a montré que $\mu + m = (\mu + \lambda) + \lambda = \mu + 2\cdot \lambda$.

En faisant partir deux tortue, l'une en 0 et l'autre en $m$, lorsque celle partant en $0$ arrivera en $\mu$ celle parti de $m$ sera en $\mu + m = \mu + 2\cdot \lambda$, donc au même point !

TBD fin

TBD

TBD

TBD

algorithme u(x: [bit]) → entier:
    (v := entier) ← 0
    (puissance_2 := entier) ← 1
    pour chaque (i := entier) de [0 .. x.longueur - 1[:
        si (x[i] == 1):
            v ← v + puissance_2
        puissance_2 ← 2 * puissance_2

    rendre v

La finitude du programme est clair. L'invariant de boucle permettant de prouver l'algorithme est : "à la fin de l'itération $i$, $v = \sum_{0 \leq k \leq i}x[i] \cdot 2^k$".

algorithme u_moins_1(n: entier) → [bit]:
    (k := entier) ← 0
    (puissance_2 := entier) ← 1
    tant que puissance_2 ≤ n:
        puissance_2 ← 2 * puissance_2
        (k := entier) ← k + 1
    
    (T := [bit]) ← [bit]{longueur: k}
    (i := entier) ← 0
    tant que n > 0:
        si n est impair:
            T[i] ← 1
            n ← n -1
        sinon:
            T[i] ← 0
        n ← n // 2
        i ← i + 1

La finitude du programme est clair. puisque dans les deux boucle on augmente (respectivement diminue) strictement une variable qui stoppe la boucle si elle devient plus grande (respectivement plus petite) qu'un seuil.

POur prouver l'algorithme, on regarde les deux boucles de l'algorithme :

• La première (lignes 4-6) est là pour connaître la longueur du tableau de bit de la sortie en cherchant la première puissance de 2 strictement plus grande que $n$. Comme il y a $\log_2(n)$ itérations de cette boucle la complexité est en $\mathcal{O}(\ln(n))$.
• La seconde crée le tableau de bit et sit exactement la définition : si $n = \sum_{i=0}^{n-1}x_i \cdot 2^i$ alors $x_i = n \pmod 2^i$.

Les deux boucles ayant $\log_2(n)$ itération et le reste des instructions étant en $\mathcal{O}(1)$ on en déduit que la complexité de l'algorithme est en $\mathcal{O}(\ln(n))$

algorithme addition(x: [bit],
                    y: [bit])  # on suppose x et y de même taille
                    → [bit]    # de la taille de x et y + 1

    (somme := [bit]) ← [bit]{longueur: x.longueur + 1}
    (retenue := bit) ← 0

    pour chaque (i := entier) de [0 .. x.longueur - 1[:
        si (x[i] == 1) et (y[i] == 1) et (retenue == 1):
            somme[i]  ← 1
            retenue ← 1
        sinon si ((x[i] == 1) et (retenue == 1)) ou ((y[i] == 1) et (retenue == 1)) ou ((x[i] == 1) et (y[i] == 1)):
            somme[i]  ← 0
            retenue  ← 1
        sinon si (x[i] == 1) ou (y[i] == 1) ou (retenue == 1):
            somme[i]  ← 1
            retenue  ← 0
        sinon:
            somme[i]  ← 0
            retenue  ← 0
    somme[x.longueur] ← retenue

    rendre somme

La preuve de correction vient du fait qu'à la fin de chaque itération, on tout se passe comme si on faisait la somme de 3 bit (x[i], y[i], et retenue)et que l'on mettait le bit unité dans somme[i] et la dizaine (en base 2) dans retenue :

          x[i]
          y[i]
+       retenue
-------------
retenue somme[i]

Les différents cas correspondes à tous les résultats possibles des additions.

Si $n$ est la taille des entrées, la complexité de l'algorithme est clairement en $\Theta(n)$. Comme l'addition nécessite au moins $\Omega(n)$ opérations pour lire les données, on est optimal.

Nos conventions veulent que x.longueur et y.longueur soient égales et comme on suppose que $u(x) \geq u(y)$ la sortie sera positive et de la même longueur que $x$.

algorithme soustraction(x: [bit],
                        y: [bit])  # on suppose x et y de même taille et que u(x) ≥ u(y)
                        → [bit]    # de la taille de x et y

    (différence := [bit]) ← [bit]{longueur: x.longueur}
    (retenue := bit) ← 0

    pour chaque (i := entier) de [0 .. x.longueur - 1[:
        si (x[i] == 1) et (y[i] == 1) et (retenue == 1):
            différence[i]  ← 0
            retenue ← 1
        sinon si ((x[i] == 1) et (retenue == 1)) ou ((x[i] == 1) et (y[i] == 1)):
            différence[i]  ← 0
            retenue  ← 0
        sinon si ((y[i] == 1) et (retenue == 1)):
            différence[i]  ← 0
            retenue  ← 1
        sinon si (x[i] == 1):
            différence[i]  ← 0
            retenue  ← 0
        sinon si ((y[i] == 1) ou (retenue == 1)):
            différence[i]  ← 1
            retenue  ← 1
        sinon:
            différence[i]  ← 0
            retenue  ← 0
          
    rendre différence

La preuve de correction vient du fait qu'à la fin de chaque itération, on tout se passe comme si on faisait x[i] - (y[i] + retenue) et que l'on mettait le bit unité dans différence[i] et la dizaine (en base 2) dans retenue :

            x[i]
- (         y[i]
   +      retenue)
----------------------
retenue différence[i]

Les différents cas correspondes à tous les résultats possibles des soustraction.

Si $n$ est la taille des entrées, la complexité de l'algorithme est clairement en $\Theta(n)$. Comme la soustraction nécessite au moins $\Omega(n)$ opérations pour lire les données, on est optimal.

Pour le premier point, on peut garder le même algorithme en copiant les entrées dans deux tableaux originellement remplis de 0 tout deux de longueurs égale au max des longueurs des deux entrées :

algorithme opération(x: [bit],
                     y: [bit])  # on suppose x et y de même taille
                     → [bit]    # de la taille de x et y + 1

    (x' := [bit]) ← [bit]{longueur: max(x.longueur, y.longueur)}
    x'[:] ← 0
    pour chaque (i := entier) de [0 .. x.longueur[:
        x'[i] ← x[i]
    (y' := [bit]) ← [bit]{longueur: max(x.longueur, y.longueur)}
    y'[:] ← 0
    pour chaque (i := entier) de [0 .. x.longueur[:
        y'[i] ← y[i]

    #  ... reste de l'algorithme

Les opérations ajoutées sont en $\mathcal{O}(max(x.\text{longueur}, y.\text{longueur}))$ ce qui ne change pas la complexité.

Pour le second point, on peut supprimer tous les derniers élément du tableaux égaux à 0 :

algorithme opération(x: [bit],
                     y: [bit])  # on suppose x et y de même taille
                     → [bit]    # de la taille de x et y + 1

    #  ... début de l'algorithme

    (i := entier) ← résultat.longueur
    (on_reste := booléen) ← Vrai

    tant que on_reste:
        si (i == 0) ou (résultat[i-1] == 1):  # on s'arrête au premier 1 ou si résultat ne contient que des 0
            on_reste ← Faux
        sinon:
            i ← i - 1
    
    (résultat' := [bit]) ← [bit]{longueur: i}

    pour chaque i de [0 .. résultat'.longueur[:
        résultat'[i] ← résultat[i]
    
    rendre résultat'

Là encore, cet ajout ne change pas la complexité de l'algorithme.

Il faut au moins lire les données, ce qui nécessite au moins $\Omega(n)$ opérations.

TBD

TBD complexité O(n) TBD algo

Nos conventions veulent que x.longueur et y.longueur soient égales, la longueur de la sortie sera donc égale à 2 fois la longueur de $x$.

On obtient l'algorithme suivant :

algorithme multiplication(x: [bit], y: [bit]) → [bit]

    (résultat := [bit]) ← [bit]{longueur: 2 * x.longueur}
    résultat[:] ← 0

    retenue := entier
    temp := entier
    pour chaque k de [0 .. x.longueur[:
        retenue ← 0
        pour chaque i de [0 .. y.longueur[:
            si y[i] == 1:
                si (x[i] == 1) et (résultat[i + k] == 1) et (retenue == 1):
                    résultat[i + k]  ← 1
                    retenue ← 1
                sinon si ((x[i] == 1) et (retenue == 1)) ou ((résultat[i + k] == 1) et (retenue == 1)) ou ((x[i] == 1) et (résultat[i + k] == 1)):
                    somme[i]  ← 0
                    retenue  ← 1
                sinon si (x[i] == 1) ou (résultat[i + k] == 1) ou (retenue == 1):
                    résultat[i + k]  ← 1
                    retenue  ← 0
                sinon:
                    résultat[i + k]  ← 0
                    retenue  ← 0
            résultat[k + x.longueur] ← retenue
    rendre résultat

La complexité de l'algorithme est en $\Theta(n^2)$ avec $n$ la longueur des 2 entrées.

TBD

algorithme Karatsuba(x: [bit], y: [bit]) → [bit]:  # x et y de même longueur
    (n := entier) ← x.longueur

    # astuce pour garantir une même taille aux tableaux si la longueur est impaire
    (x1 := [bit]) ← [bit]{longueur: n // 2 + (n mod 1)}
    x1[-1] ← 0
    x1[: n // 2] ← x[: n // 2]
    (x2 := [bit]) ← [bit]{longueur: n // 2 + (n mod 1)}
    x2[n // 2 :] ← x[n // 2 :]

    (y1 := [bit]) ← [bit]{longueur: n // 2 + (n mod 1)}
    y1[-1] ← 0
    y1[: n // 2] ← y[: n // 2]
    (y2 := [bit]) ← [bit]{longueur: n // 2 + (n mod 1)}
    y2[n // 2 :] ← y[n // 2 :]

    (x2y2 := [bit]) ← Karatsuba(x2, y2)
    (x1y1 := [bit]) ← Karatsuba(x1, y1)

    (x1y2 := [bit]) ← Karatsuba(x1, y2)
    (x2y1 := [bit]) ← Karatsuba(x2, y1)

    résultat := [bit]

    résultat ← puissance(n, x2y2)
    résultat ← somme(résultat, puissance(n // 2, somme(x1y2, x2y1)))
    résultat ← somme(résultat, x1y1)

TBD

TBD

TBD

TBD

algorithme Karatsuba(x: [bit], y: [bit]) → [bit]:  # x et y de même longueur
    (n := entier) ← x.longueur

    # astuce pour garantir une même taille aux tableaux si la longueur est impaire
    (x1 := [bit]) ← [bit]{longueur: n // 2 + (n mod 1)}
    x1[-1] ← 0
    x1[: n // 2] ← x[: n // 2]
    (x2 := [bit]) ← [bit]{longueur: n // 2 + (n mod 1)}
    x2[n // 2 :] ← x[n // 2 :]

    (y1 := [bit]) ← [bit]{longueur: n // 2 + (n mod 1)}
    y1[-1] ← 0
    y1[: n // 2] ← y[: n // 2]
    (y2 := [bit]) ← [bit]{longueur: n // 2 + (n mod 1)}
    y2[n // 2 :] ← y[n // 2 :]

    (x2y2 := [bit]) ← Karatsuba(x2, y2)
    (x1y1 := [bit]) ← Karatsuba(x1, y1)

    (s1 := [bit]) ← somme(x1, x2)
    (s2 := [bit]) ← somme(y1, y2)
    (p := [bit]) ← Karatsuba(s1, s2)

    résultat := [bit]

    résultat ← puissance(n, x2y2)
    résultat ← somme(résultat, puissance(n // 2, x2y2))
    résultat ← soustraction(résultat, somme(x2y2, x1y1))

Il y a 3 appels à l'algorithme avec des tableaux de tailles divisées par deux et le reste des algorithmes appelés et des opérations est en $\mathcal{O}(n)$

TBD

TBD

Comme $\log_2(3) \simeq 1.58$, l'algorithme de Karatsuba est de complexité $\mathcal{O}(n^{1.59})$, strictement plus petite que l'algorithme naïf de multiplication en $\mathcal{O}(n^{2})$.