In [1]:
# Pensez à évaluer cette cellule : `Shift-Entrée`
import matplotlib.pyplot as plt
%matplotlib inline
plt.style.use('seaborn')

import math

Prendre un papier et un stylo, et montrer les récurrences pour $n:=2^k$ (soit $k=log_2(n)$)

Factorielle, exponentiation naïve

$\begin{cases} C(n) = C(n-1) + 1\\ C(1) = 1 \end{cases}$

On montre par récurrence que $\forall n \geq 1, C(n)=n$ donc $C(n) = O(n)$

In [2]:
def C(n):
    assert n >= 1
    if n==1: return 1
    return C(n-1)+1

print(', '.join("C({})={}".format(n, C(n)) for n in range(1, 8)))
plt.plot([C(n) for n in range(1, 10)])

C(1)=1, C(2)=2, C(3)=3, C(4)=4, C(5)=5, C(6)=6, C(7)=7
Out[2]:
[<matplotlib.lines.Line2D at 0x7fe07f4d1400>]

Dichotomie

Si on ne fait pas de slicing n'importe comment...

$\begin{cases} C(n) = C\left(\frac{n}{2}\right) + 1\\ C(1) = 1 \end{cases}$

On montre par récurrence que $\forall k \geq 0, C(2^k)=k+1$ donc $C(n)=O(\log_2(n))$

In [3]:
def C(n):
    assert n >= 1
    if n==1: return 1
    return C(n//2)+1

print(', '.join("C({})={}".format(2**k, C(2**k)) for k in range(8)))
plt.plot([C(n) for n in range(1, 100)])
plt.plot([math.log(n, 2) for n in range(1, 100)], label=r'$n \mapsto \log_2(n)$')
plt.plot([math.log(n, 2)+1 for n in range(1, 100)], label=r'$n \mapsto \log_2(n)+1$')
plt.legend()

C(1)=1, C(2)=2, C(4)=3, C(8)=4, C(16)=5, C(32)=6, C(64)=7, C(128)=8
Out[3]:
<matplotlib.legend.Legend at 0x7fe07edac6a0>

Fausse dichotomie

Un sorte de dichotomie pas très utile... où on irait chercher l'élément dans les sous-tableaux gauche et droit

$\begin{cases} C(n) = 2 \times C\left(\frac{n}{2}\right) + 1\\ C(1) = 1 \end{cases}$

On montre par récurrence que $\forall k \geq 0, C(2^k)=2^k$ donc $C(n) = O(n)$

In [4]:
def C(n):
    assert n >= 1
    if n==1: return 1
    return 2*C(n//2)+1

print(', '.join("C({})={}".format(2**k, C(2**k)) for k in range(8)))
plt.plot([C(n) for n in range(1, 100)])
plt.plot([n for n in range(1, 100)], label=r'$n \mapsto n$')
plt.plot([2*n for n in range(1, 100)], label=r'$n \mapsto 2 \times n$')
plt.legend()

C(1)=1, C(2)=3, C(4)=7, C(8)=15, C(16)=31, C(32)=63, C(64)=127, C(128)=255
Out[4]:
<matplotlib.legend.Legend at 0x7fe07ecb29b0>

Tri fusion, Tri rapide

  • Si on choisit "bien" le pivot pour le tri rapide (médiane)

$\begin{cases} C(n) = 2 \times C\left(\frac{n}{2}\right) + n\\ C(1) = 1 \end{cases}$

On montre par récurrence que $\forall k \geq 0, C(2^k)=2^k \times (k+1)$ donc $C(n) = O(n.log_2(n))$

In [6]:
def C(n):
    assert n >= 1
    if n==1: return 1
    return 2*C(n//2)+n

N = 1000
print(', '.join("C({})={}".format(2**k, C(2**k)) for k in range(8)))
plt.plot([C(n) for n in range(1, N)])
plt.plot([n*(math.log(n, 2)+1) for n in range(1, N)], label=r'$n \mapsto n.(\log_2(n)+1)$')
plt.plot([n*(math.log(n, 2)-1) for n in range(1, N)], label=r'$n \mapsto n.(\log_2(n)-1)$')
plt.legend()

C(1)=1, C(2)=4, C(4)=12, C(8)=32, C(16)=80, C(32)=192, C(64)=448, C(128)=1024
Out[6]:
<matplotlib.legend.Legend at 0x7fe07eb8bb38>
In [ ]: