On considère un ensemble de k
données stockés dans un tableau de données statique T
de N
cases (avec 0
≤k
≤ N
).
Remarques :
0
à N-1
i
est un indice de case, T[i]
désigne le contenu de la caseN
est fixé mais k
varie en fonction du nombre de données stockées
Propriété 1 : les données sont stockés dans les k
premières cases du tableau. Ainsi, les cases de 0
à k-1
sont occupées et l'indice k
désigne la première case libre.
Ecrire un algorithme permettant d’insérer une nouvelle donnée t
dans le tableau T
en conservant la propriété 1. Quelle est sa complexité?
Propriété 2 : il n’y a pas de doublons dans le tableau, autrement dit ∀ i
,j
< k
, si i
≠ j
alors T[i]
≠ T[j]
.
Ecrire un algorithme permettant d’insérer une nouvelle donnée t
dans le tableau T
en conservant les propriétés 1 et 2. Quelle est sa complexité?
Propriété 3 : On suppose qu’il existe un ordre ≺ sur les données. ∀ i
,j
< k
, si i
< j
alors T[i]
≺ T[j]
.
Écrire un algorithme permettant d’insérer une nouvelle donnée t
dans le tableau T
en conservant les propriétés 1, 2 et 3. Quelle est sa complexité?
Un algorithme de recherche prend en argument une donnée t
et retourne :
t
si t
est présent dans le tableau-1
sinon ("donnée absente")Écrire un algorithme de recherche sachant que la propriétés 1 est respectée, un algorithme de recherche sachant que les propriétés 1 et 2 sont respectées, puis un algorithme de recherche sachant que les propriétés 1 et 2 et 3 sont respectées. Quelle est leur complexité?
Un algorithme de suppression prend en argument une donnée t
et :
t
du tableau si t
est présent dans le tableauÉcrire un algorithme de suppression conservant la propriétés 1, un algorithme de suppression conservant les propriétés 1 et 2, puis un algorithme de suppression conservant les propriétés 1 et 2 et 3. Quelle est leur complexité?
On appelle liste une structure abstraite ordonnée telle que l'on puisse accéder de manière directe à l'élément i
et à laquelle on puisse ajouter (et supprimer) autant d'éléments que l'on souhaite. Une caractéristique importante de cette structure est son nombre d'éléments.
Une implémentation des listes peut être effectuée comme suit:
n
= 1, le nombre initial d'éléments étant k
= 0k < n
,k
k
← k + 1
2 * n
éléments et n
← n * 2
k
premiers éléments du tableau initial dans le nouveau tableau & supprimer le tableau initial.k
k
← k + 1
Montrez que la complexité de l’ajout de k
éléments à la fin d’une liste originellement vide est O(k
).
La structure de données utilisée ici est la liste. On considérera que la création d’une liste vide, l’ajout d’un élément en fin de liste & la lecture d’un élément dans une liste se font en O(1) opérations.
L
& une valeur val
.L2
, restriction de L
aux valeurs différentes de val
.L
.L2
ne contenant qu’une seule occurrence de chaque valeur de L & en conservant le même ordre.L
en entrée est triée. Donnez un algorithme en O(n) pour résoudre ce problème, où n
est le nombre d’ ́éléments de L
.L2
n’est pas important, proposez une meilleure solution à la question du point 2.
On considère comme dans l'exercice 1 un tableau statique de données T
de taille N
. A la différence de l'exercice 1,
T
peut contenir entre 0
et n
données0
≤ k[i]
≤ n
est le nombre d'éléments contenus dans la case i
0
≤ K
≤ N
est le nombre de cases effectivement occupées (la valeur de K peut varier au cours du temps). t
dans une case i
quelconque en temps constant i
,j
< K
, si i
< j
alors ∀ t ∈ T[i]
, ∀ s ∈ T[j]
, t ≺ s
), montrez qu'il est possible d'insérer une donnée dans le tableau en O(log K).