Discussion :

[adel01]

bien le salut a vous
voila je suis sur un cour d'algo et je n'arrive pas a assimilé ce que c'est qu'un exemple de compléxité linéaires?
quelqu'un peut-il me l'expliqué svp?
amicalement adel

[souviron34]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
pour tout i de 0 à N
   result = result + i

[millie]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
pour tout i de 0 à N
   result = result + i

Alors je vais faire mon chiant, mais pour moi, cet algo est de complexité exponentielle et non linéaire.

On dit qu'une complexité est linéaire si la complexité est en O(t) ou t est la taille de l'entrée. Comme la taille d'un entier n est en t= log(n), la complexité est donc O(n) = O(exp(t)), et donc exponentielle par rapport à la taille de l'entrée.



En revanche, l'algo suivant est de complexité linéaire car l'entrée est un tableau de taille n :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Entrée : tableau de taille n
 
Pour i= 0 à taille(tableau)
   ....

[pseudocode]

On dit qu'une complexité est linéaire si la complexité est en O(t) ou t est la taille de l'entrée.

???

Je ne vois pas pourquoi "entrée" serait forcément synonyme de "longueur" d'un tableau ou d'un champ de bits

[millie]

???

Je ne vois pas pourquoi "entrée" serait forcément synonyme de "longueur" d'un tableau ou d'un champ de bits

Je veux dire que quand on parle de complexité polynomiale, linéaire, exponentielle, c'est toujours par rapport à la taille de l'entrée (ou de l'instance ou de la donnée).

Après, on parle de complexité suivant ce qu'on veut.
L'exemple de souviron est linéaire par rapport à n. Mais n'est pas à proprement parler linéaire tout court.

Bon, c'est nase, mais dire que l'algorithme est de complexité polynomiale (classe P) est différent de dire qu'il est de complexité polynomiale par rapport à n (enfin, classe P, c'est pour les problèmes et non les algorithmes)

Toute façon, c'est l'heure de l'apéro

[souviron34]

Toute façon, c'est l'heure de l'apéro

je pense que ça devrait être du café, plutôt...

Alors je vais faire mon chiant, mais pour moi, cet algo est de complexité exponentielle et non linéaire.
....

Soit le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
pour tout i de 0 à N
   result = result + i

et le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Entrée : tableau de taille n
 
Pour i= 0 à taille(tableau)
   ....

Si je dis que mon tableau est de taille N , et que je veux en faire la somme, je pars de ton code , et je remplace tes points de suspension par s=tab[n]+s... et j'arrive au mien, avec la même complexité.... linéaire..

[Alp]

Pour le PO :
voici un algo qui calcule la somme des éléments d'un tableau T de N éléménts (tableau qui commence à l'indice 0) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
resultat := 0
Pour i = 0 à N-1
  resultat = resultat + T[i]
Fin Pour

où T[i] est donc le (i+1)-ème élément du tableau.

Linéaire car le temps nécessaire pour calculer ceci est une fonction de la taille du tableau (et non pas du carré de la taille du tableau, de l'exponentielle de la taille du tableau, ...) : si l'on multiplie par 2 la taille du tableau, l'algorithme mettra 2 fois le temps qu'il mettait dans le cas précédent.

[FR119492]

Salut!

si l'on multiplie par 2 la taille du tableau, l'algorithme mettra 2 fois le temps qu'il mettait dans le cas précédent.

Théoriquement ...
Jean-Marc Blanc

[Alp]

Salut!

Théoriquement ...
Jean-Marc Blanc

Oui oui, biensûr. J'ai hésité à rajouter "grossièrement" dans ma phrase.

[millie]

avec la même complexité.... linéaire..

Quand on parle d'algorithme de complexité linéaire. Et pas de complexité linéaire en fonction de quelque chose, c'est qu'on parle par rapport à la taille de l'entrée. Car parler de complexité linéaire tout court n'aurait pas de sens si ce n'était pas en fonction de quelque chose.

Tout comme la classe P correspond à l'ensemble des problèmes que l'on peut résoudre par un algorithme de complexité polynomiale par rapport à la taille de l'entrée.

D'un côté, on a en entrée un entier n de taille log2(n) et de l'autre un tableau de taille n. Donc la complexité par rapport à la taille de l'entrée est différente. Mais les 2 complexités sont linéaires en fonction de n.

[pseudocode]

Quand on parle d'algorithme de complexité linéaire. Et pas de complexité linéaire en fonction de quelque chose, c'est qu'on parle par rapport à la taille de l'entrée. Car parler de complexité linéaire tout court n'aurait pas de sens si ce n'était pas en fonction de quelque chose.

Certes. C'est un peu tiré par les cheveux quand même.

La notation usuelle de la complexité linéaire étant O(n), il n'y a pas d'ambiguïté sur l'entrée "n" dont on parle.

[millie]

J'ai précisé :

je vais faire mon chiant

[souviron34]

certes..

Mais le PO pose une question banale, la réponse devrait être simple..

Et elle l'est..

Je sais bien que Jussieu a eu le prix Ignobel de Physique il y a peu pour avoir étudié pourquoi les spaghettis se cassaient plus qu'en 2 quand on les pliaient, mais ce n'est pas une raison pour faire dériver un sujet simple en une abracadabrantesque élucubration sur le sens du mot "complexité"...

[cedriku]

Bonjour,

alors si on chipote comme ca (meme si sur le fond je suis d'accord avec millie pour dire qu'une complexité lineaire ne veut rien dire si on ne dit pas en quel parametre), on devrait plutot dire que la complexité d'une somme de 2 entiers x et y est en O(log2(max{x,y})). Dans notre cas, result vaut au maximum n(n+1)/2 donc l'operation a l'interieur de la boucle se fait en O(log2(n^2)) ce qui equivaut en O(log2(n)). Cette operation se faisant n fois, on a au final que l'algo est en O(n*log2(n)). Donc l'algo est quasi-lineaire en le nombre n. Mais il est evident que l'on considere souvent les operations de bases comme se faisant en temps constant d'ou le fait que l'on dit que c'est lineaire en n tout court.

Et puis apres il faut alors aussi chipoter sur : est ce que l'on est sur une machine de turing deterministe ou non-deterministe ? Car un algo en O(exp(n)) sur une MTD devient O(n) sur une MTND.

Si on devait tout preciser lorsque l'on parle de complexité... ca deviendrait lourd.

[millie]

Ca fait 2 fois que vous parlez de PO. C'est quoi ?

[Alp]

Posteur Original, celui qui a créer ce sujet quoi