On 2008-10-01, candide <candide@free.invalid> wrote:

Marc Boyer a écrit :

J'ai employé le terme de liste dans un sens informel, ça ne change rien
au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au
sens informel encore).

  Et pourtant ça change plein de choses, en algorithmique déjà,

"Plein de choses", ça se discute parce que ça dépend du point de vue ou
de la hauteur où tu te places.

  Je ne connais pas tant de points de vue que cela en algorithmique.

Un algorithme change-t-il vraiment si la structure de données est
une liste ou un tableau ?

  Ben, une recherche par dichotomie dans un tableau, c'est O(log n),
et dans une liste chainée, c'est O(n).

Le tri par insertion
ou le tri fusion s'implémentent plus facilement avec une liste certes
mais il me semble que la complexité n'est pas modifiée, la liste va
juste t'épargner des recopies mais les algorithmes dans leur principe
restent strictement identiques. Idem quand tu travailles avec des
graphes, que tu travailles avec des matrices d'adjacence ou des listes
d'adjacence, l'algorithme de Dijkstra reste l'algorithme de Disjstra.
Idem pour les nuances qu'on peut faire entre itératif et récursif, un
DFS reste un DFS.

  Enumerer les cas où les différences sont faibles ne dit pas que
les choses sont identiques.
  Dans un tableau, un acces quelconque est en O(1) et une insertion
en O(n), et l'inverse pour les listes.
  Si un algo fait autant d'insertion que d'accès, ça donnera la même
chose. De même, s'il fait des acces "en séquence" et pas d'insertion.

 

et en C encore plus.

De toute façon en C, la notion de liste chainée n'existe pas

  Dans la norme C, non. Mais dans les programmes en C, souvent, il y
en a. Idem pour des choses comme "complexité", "performance', etc.

Et puis un jour faudra qu'on discute des réels avantages
des listes chaînées, je trouve ça souvent très couteux (multiples malloc
et free faits séquentiellement).

  Si tu veux.

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
                           IF -- Rudyard Kipling (Trad. André Maurois)