« Programmation algorithmique/Nombre d'opérations optimal » : différence entre les versions

Toutes les complexités indiquées ici valent pour des machines séquentielles, c'est à dire une machine munie d'un seul processeur, ou bien une machine multi-processeurs sur laquelle on n'utiliserait qu'un seul cœur. D'ailleurs, le langage algorithmique que nous utilisons décrit uniquement des séquences d'intructionsd’instructions et d'opérations.

Notons que le facteur d'accélération amené par une machine parallèle, c'est-à-dire munie de plusieurs processeurs, est limité. Par exemple, pour une machine à 64 processeur, on peut espérer aller 64 fois plus vite au maximum. Pour un algorithme en <math>O(2^{n})</math> et <math>n</math> valant 100, le nombre d'opérations sur une machine séquentielle est de l'ordre de <math>2^{100}</math>, tandis que sur une machine à 64 processeurs on peut espérer un ordre de <math>(2^{100})/64</math> soit <math>(2^{100})/(2^{6})</math> ou <math>2^{94}</math> opérations. On voit bien ici que le le nombre de processeurs, forcément limité, n'influence pas forcément la complexité en temps. Ceci s'explique également par le fait qu'un facteur multiplicatif constant (ici <math>1/64</math>) est négligeable devant un carré ou une exponentielle quand la taille du problème devient grande.