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..