TD3 : Complexité amortie

Énoncé

TD 3

EX 1

1) On tient à jour deux piles :

  • une pile d’entrée
  • une pile de sortie, qu’on dépile pour faire office de file

Étape 1 : on ajoute $k$ éléments dans la pile d’entrée

Étape 2 : on dépile les $k$ éléments de la pile d’entrée, et on les empile dans la pile de sortie

Étape 3 : on dépile les éléments de la pile de sortie (c’est notre file).

(on ajoute les éléments de la pile d’entrée dans la pile de sortie que quand elle est vide)

2) Linéaire en le nombre $n$ d’éléments.

3) Potentiel : 2 (nombre total d’éléments - nombre d’éléments de la pile de sortie).

Empiler :

  • $t(Empiler) = 1$, et $Pot$ croît de $2$ ⟹ $a(Empiler) = 3$

Dépiler :

  • Si la pile de sortie est non vide : $t(Dépiler) = 1$, et $Pot$ augmente de $0$ ⟹ $a(Dépiler) = 1$
  • Si la pile de sortie est vide : $t(Dépiler) = 2n+1$, et $Pot$ diminue de $2n$ ⟹ $a(Dépiler) = 1$

Potentiel : 2 fois le nombre d’éléments de la pile d’entrée.

\[a(ajout) = 1 + Pot_{final} - Pot_{initial} \\ = 1 + 2 = 3\] \[a(suppression) = 1 + 𝛥Pot \\ = \begin{cases} 1 + 0 \text{ si $P_{sortie}$ non vide} \\ 1 + 2n - 2n \text{ sinon } \\ \end{cases} \\ = 1\]

EX 2

1)

def empiler1(Stack, top, x):
    n = len(Stack)
    if top == n :
        NewStack = []*2n
        for i in range(n):
            NewStack[i] = Stack[i]
        top +=1
        NewStack[top] = x

2) Si $n$ est le nombre d’éléments de la liste, la complexité dans le pire des cas vaut $n+1$.

3) Potentiel : $top-n$

\[a(empiler) = 1 + 𝛥Pot \\ = \begin{cases} 1 + 1 \text{ si $Stack$ non remplie} \\ n+1 - (n-1) \text{ sinon } \\ \end{cases} \\ = 2\]

4)

Plus $k$ à chaque fois

def empiler2(Stack, top, x):
    global k
    n = len(Stack)
    if top == n-1 :
        NewStack = []*(n+k)
        for i in range(n):
            NewStack[i] = Stack[i]
        top +=1
        NewStack[top] = x

Potentiel : $top-n$

\[a(empiler) = 1 + 𝛥Pot \\ = \begin{cases} 1 + 1 \text{ si $Stack$ non remplie} \\ n+1 - (k-1) = n-k+2 \text{ sinon } \\ \end{cases}\]

M2 :

Avec Potentiel : $top^2-n^2$ : $a(empiler) = O(i)$ dans tous les cas.

Heuristique :

  1. Intuiter une complexité naïve de l’algorithme (ici: quadratique, pour $k$ petit)
  2. Le potentiel est une différence de variables à l’exposant correspondant (ici: $top^2-n^2$) [⟶ Primitive discrète]
  3. La complexité, dans tous les cas, doit être la même : [⟶ Dérivée discrète du potentiel]

BUT : Il faut que dans tous les cas, la complexité amortie ne varie pas (pour simplifier le calcul de la somme (sur $i$) dans la complexité).

5)

def empiler3(Stack, top, x):
    n = len(Stack)
    if top == n-1 :
        NewStack = []*(n**2)
        for i in range(n):
            NewStack[i] = Stack[i]
        top +=1
        NewStack[top] = x

Potentiel : $top-n$

\[a(empiler) = 1 + 𝛥Pot \\ = \begin{cases} 1 + 1 \text{ si $Stack$ non remplie} \\ n+1 - (n^2-n-1) = -(n+1)^2+4n+3 \text{ sinon } \\ \end{cases}\]

6)

a)

def depiler1(Stack, top, x):
    n = len(Stack)
    if top == n/2 :
        NewStack = []*(n/2)
        for i in range(n/2):
            NewStack[i] = Stack[i]
        top +=1
        NewStack[top] = x

Fausse piste :

Potentiel : $top-n$

\[a(dépiler) = 1 + 𝛥Pot \\ = \begin{cases} 1 - 1 \text{ si $Stack$ assez remplie} \\ n/2 + (top-1-n/2) - (top-n) = n \text{ sinon } \\ \end{cases}\]

: Pas bon

b) Si : on recopie $n/4$ éléments, et taille du tableau : $n ⟶ n/4$ :

def depiler2(Stack, top, x):
    n = len(Stack)
    if top == n/4 :
        NewStack = []*(n/2)
        for i in range(n/4):
            NewStack[i] = Stack[i]
        top +=1
        NewStack[top] = x

Potentiel : $top-n$

\[a(dépiler) = 1 + 𝛥Pot \\ = \begin{cases} 1 - 1 \text{ si $Stack$ assez remplie} \\ n/4 + (top-1-n/2) - (top-n) = O(3n/2) \text{ sinon } \\ \end{cases}\]

: pas bon

Si $Pot= 𝛽n-k$, on veut que \(n(𝛽/2 + 1/4) = 0\)

Potentiel : $n/2-top$ quand $top < n/2$, et on revient à $top-n$ sinon

\[a(dépiler) = 1 + 𝛥Pot \\ = \begin{cases} 1 + 1 \text{ si $Stack$ assez remplie} \\ n/4 + (n/4-top+1) - (n/2-top) = O(1) \text{ sinon } \\ \end{cases}\]

7)

Potentiel : $top-n$

\[a(empiler) = 1 + 𝛥Pot \\ = \begin{cases} 1 + 1 \text{ si $Stack$ non remplie} \\ n+1 - (3n-1) = -2n +2 \text{ sinon } \\ \end{cases}\] \[a(dépiler) = 1 + 𝛥Pot \\ = \begin{cases} 1 - 1 \text{ si $Stack$ assez remplie} \\ n/4+1 - (n/4-1) = 2 \text{ sinon } \\ \end{cases}\]

EX 3

1) Complexité en $O(n)$ (exactement : $\lfloor n/2 \rfloor$) 2) \(P(w \text{ est palindrome}) = \frac{k^{\lfloor n/2 \rfloor}}{k^n} = \frac{1}{k^{n-\lfloor n/2 \rfloor}}\)

3) \(\begin{align*} E &= \sum_{\text{1-quasi-palindromes}} 1 \times \frac{k^{n-1}}{k^n} \\ &+ ⋯ \\ &+ \sum_{(\lfloor n/2 \rfloor-1)\text{-quasi-palindromes}} (\lfloor n/2 \rfloor-1) \frac{k^{n-\lfloor n/2 \rfloor+1}}{k^{n}} \\ &+ \sum_{\text{palindromes} = \lfloor n/2 \rfloor\text{-quasi-palindromes}} \lfloor n/2 \rfloor \frac{k^{n-\lfloor n/2 \rfloor}}{k^n} \\ &= \frac{1}{k^{n-2(n-1)}} \\ &+ ⋯ \\ &+ (\lfloor n/2 \rfloor-1) \frac{1}{k^{n-2(n-\lfloor n/2 \rfloor+1)}} \\ &+ \lfloor n/2 \rfloor \frac{}{k^{n-2(n-\lfloor n/2 \rfloor)}} \\ &= \sum\limits_{i=1}^{\lfloor n/2 \rfloor} \frac{i}{k^{n-2(n-i)}} \\ &= \sum\limits_{i=1}^{\lfloor n/2 \rfloor} \frac{i}{k^{2i-n}} \\ &= k^{n-2} \frac{d}{dx}\Bigg [ \sum\limits_{i=1}^{\lfloor n/2 \rfloor} x^i \Bigg]_{x=1/k^2} \\ &= k^{n-2} \frac{d}{dx}\Bigg [ x \frac{x^{\lfloor n/2 \rfloor}-1}{x-1}\Bigg]_{x=1/k^2} \\ &= k^{n-2} \frac{d}{dx}\Bigg [ x \frac{x^{\lfloor n/2 \rfloor}-1}{x-1}\Bigg]_{x=1/k^2} \\ \end{align*}\)

EX 4

En place :

def quick_sort(L, min = 0, max= -1):
  assert L
  if max >= min:
    if max == -1:
      max = len(L)-1
    p = L[min]
    p, L[max] = L[max], p
    i = 0
    for j in range(max):
      if L[j] <= p:
        L[j], L[i] = L[i], L[j]
        i+=1
    L[i+1], p = p, L[i+1]
    quick_sort(L, min, i)
    quick_sort(L, i+2, max)

Leave a comment