In [1]:
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
In [2]:
def instructionSimple(n):
cnt = 0
cnt += 1
return cnt
In [3]:
samples = range(1,1000,10)
C0 = [ instructionSimple(i) for i in samples]
plt.title('Complexité constante')
plt.plot(samples,C0)
plt.show()
In [4]:
def boucleSimple(n):
cnt = 0
for i in range(0,n):
cnt += 1
return cnt
In [5]:
C1 = [ boucleSimple(i) for i in samples]
plt.title('Complexité linéaire')
plt.plot(samples,C1)
plt.show()
In [6]:
def bouclesImbriquees(n):
cnt = 0
for i in range(0,n):
for j in range(0,n):
cnt += 1
return cnt
In [7]:
C2 = [ bouclesImbriquees(i) for i in samples]
plt.title('Complexité quadratique')
plt.plot(samples,C2)
plt.show()
In [8]:
plt.title('Complexités constante, linéaire et quadratique')
plt.loglog(samples,C2,label='boucles imbriquées')
plt.loglog(samples,C1,label='boucle simple')
plt.loglog(samples,C0,label='instruction simple')
plt.legend()
plt.show()
In [9]:
def enchainement(n):
cnt = 0
cnt += 1
for i in range(0,n):
cnt += 1
for i in range(0,n):
for j in range(0,n):
cnt += 1
return cnt
In [10]:
C3 = [ enchainement(i) for i in samples ]
plt.title('Complexité de l\'enchainement')
plt.loglog(samples,C3,label='enchainement')
plt.loglog(samples,C2,label='boucles imbriquées')
plt.loglog(samples,C1,label='boucle simple')
plt.loglog(samples,C0,label='instruction simple')
plt.legend()
plt.show()
In [11]:
def triangle(n):
cnt = 0
for i in range(0,n):
for j in range(0,i):
cnt += 1
return cnt
In [12]:
C4 = [ triangle(i) for i in samples ]
plt.title('Complexité de la boucle triangulaire')
plt.loglog(samples,C4,label='triangle')
plt.loglog(samples,C2,label='boucles imbriquées')
plt.loglog(samples,C1,label='boucle simple')
plt.legend()
plt.show()
In [13]:
def logarithmique(n):
cnt = 0
while n >= 1:
cnt += 1
n /= 2
return cnt
In [14]:
C5 = [ logarithmique(i) for i in samples ]
plt.title('Complexité logarithmique')
plt.plot(samples,C5,label='logarithmique')
plt.plot(samples,C1,label='linéaire')
plt.plot(samples,C0,label='constante')
plt.ylim(0,20)
plt.legend()
plt.show()
In [15]:
def linearithmique(n):
cnt = 0
for i in range(0,n):
j = n
while j >= 1:
cnt += 1
j /= 2
return cnt
In [16]:
C6 = [ linearithmique(i) for i in samples ]
plt.title('Complexité linéarithmique')
plt.loglog(samples,C6,label='linéarithmique')
plt.loglog(samples,C2,label='quadratique')
plt.loglog(samples,C1,label='linéaire')
plt.loglog(samples,C0,label='constante')
plt.legend()
plt.show()
In [17]:
import random
def alternatif(n):
cnt = 0
for i in range(n):
if random.randint(0,n) == 0:
for j in range(n):
cnt += 1
else:
cnt += 0
return cnt
In [18]:
C7 = [ 0 for i in samples ]
nrTests = 20
for test in range(0,nrTests):
C7 = [ c7 + alternatif(i) / nrTests for i,c7 in zip(samples,C7) ]
plt.title('Complexité enchainement alternatif')
plt.loglog(samples,C7,label='alternatif')
plt.loglog(samples,C1,label='linéaire')
plt.legend()
plt.show()
In [19]:
def alternatif2(n):
cnt = 0
p2 = 1
for i in range(0,n):
if i == p2:
for j in range(0,p2):
cnt += 1
p2 *= 2
return cnt
In [20]:
C8 = [ alternatif2(i) for i in samples ]
plt.title('Complexité enchainement alternatif')
plt.loglog(samples,C8,label='alternatif2')
plt.loglog(samples,C1,label='linéaire')
plt.legend()
plt.show()
