Cours Stage - Recherche d'une occurence

Exercice - Recherche d'une occurrence

L'énoncé

Répondre aux questions suivantes. 


Question 1

Donner la fonction recherche(L, a) en s'inspirant de l'algorithme du cours, qui recherche par balayage la présence de la valeur $a$ dans le tableau $L$. 

On donne la fonction en s'inspirant de l'algorithme du cours :

def recherche(L, a):
  n = len(L)
  i = 0
  while i < n and a != T[i]:
    i = i + 1
  if i < n :
    return i

On pourra s'aider de la vidéo du cours. 

Question 2

Donner et démontrer la complexité de l'algorithme dans le pire des cas. 

Le pire des cas est le cas qui nécessite le plus d'opérations élémentaires : c'est à dire lorsque l'algorithme balaie toute la liste $L$.
Ainsi, le balayage de l'ensemble de la liste $L$ nécessite $n$ comparaisons et $n$ additions. On compte également le test pour retourner une valeur ou non. Ainsi, il y a $2n + 1$ opérations élémentaires : c'est donc un algorithme de complexité linéaire. 

On pourra commencer par réfléchir au sens de pire des cas. 

Question 3

Donner une fonction nb_occurrence(L, a) qui donne retourne une liste [a, x] ou x est le nombre d'apparition de a dans L.

La fonction est la suivante : 

def nb_occurrence(L, a):
  x = 0
  for i in L:
    if i == a:
      x+=1
  return [a, x]

On pourra parcourir la liste et comparer chaque élément à $a$. 

Question 4

Ecrire une fonction nombre_tot_apparition(L) qui permet de retourner le nombre d'occurrences de chaque élément de la liste sous la forme d'une matrice contenant sur la première colonne l'élément et sur la deuxième son nombre d'apparition. 

def nombre_tot_apparition(L):
  liste_apparition = [[L[0], 0]]
#matrice qui contiendra les éléments et leur nombre d'apparition respectif
  for i in L:
#on parcourt tous les éléments de L
    n = len(liste_apparition)
    j = 0
    while j < n and i != liste_apparition[j][0]:
#on regarde si l'élément i appartenant à L a déjà été rencontré et appartient donc à liste_apparition
      j+= 1
    if j < n :
#cela signifie que l'on a trouvé l'élément dans la liste de comptage
      liste_apparition[j][1]+= 1
#on éléve le nombre d'apparition de i de 1
    else :
      liste_apparition.append([i, 1])
#c'est la première fois qu'il apparait, donc son nombre d'apparition est fixé à 1
  return liste_apparition

On pourra créer une matrice qui contiendra les éléments et leur nombre d'apparition respectif


On parcourra la liste L élément par élément et on regardera si ce dernier est déjà apparu (dans quel cas on augmentera de 1 son nombre d'apparition), sinon on le rajoute à la liste. 


On pourra utiliser le principe de l'algorithme du cours.

Question 5

Que dire de la complexité de la fonction précédente ? 

On se place dans le cas où chaque élément de la liste est différent. 
Ainsi, lorsque l'on regarde le $p$ième élément de la liste, on effectue $p$ comparaisons dans la liste annexe car le $p$ième élément n'apparait pas. Cela revient donc à sommer $1 + 2 + 3+ ... + n = \dfrac{n(n + 1)}{2} \approx n^2$ quand $n$ est grand. 
Il y a donc environ $n^2$ comparaisons. 
Selon le même raisonnement, on montre qu'il y a $n^2$ additions.
Enfin, il y a $n$ affectations dans la liste annexe.
Au final, il s'agit donc d'un algorithme quadratique dans le pire des cas. On note donc que le cas pire est en $\mathcal{O}(n^2)$. 

On pourra se placer dans le cas où tous les éléments sont différents.