Calcul de complexité

**WhiteCrow** · 09/12/2020, 23h21

Envoyé par antares56

Ok donc si j'ai compris la méthode:
pour celle là

Code :

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

1
2
3
4
5
 
int f(int [] t){
int j=t.length * t.length;
return j;
}

C'est du O(1) (car opération élémentaire)

Oui¹

Envoyé par antares56

pour celle là

Code :

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

1
2
3
4
5
6
7
8
9
 
void f(int [] t){
int i=t.length-1;
while(i<t.length && i>0){
if (t[i]>=0 && t[i]<t.length){
i=t[i];
} else { i=0; }
}
}

C'est du O(N)

mmm … comment dire ... pourquoi n'essayes-tu pas de faire une trace pour te donner une idée … par exemple avec t={0} ou t={5,4,3,2,1,0} ou t={10,20,30} …

Envoyé par antares56

Code :

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

1
2
3
4
5
6
7
8
9
 
void f(int [] t){
int m= t.length;
int res= 0;
while (m>0){
m=m/2;
res=res+1;
}
}

Et celle là du O(1) aussi ?

à nouveau il faut faire une trace pour se faire une idée ; mais basiquement on se dit que ça va surtout dépendre de la valeur de m qui influe sur le nombre de tour de boucles, et de quoi dépend la valeur de m ?

¹: on part du principe que l'accès à la donnée t.length se fait en temps constant évidemment. Cela est courant lorsqu'il s'agit d'un tableau ; mais il faut faire attention car ce n'est absolument pas le cas pour d'autres sdd classiques comme les listes simplement chaînée par exemple.

**antares56** · 09/12/2020, 23h42

Pour la 2 si j'essaye avec le t = {10,20,30};
i = 2
donc le while est valide on passe au if
si t[2] > = 0 && t[2]<t.length) donc le if n'est pas valide car t[2] n'est pas plus grand que t.length
ensuite on va direct dans le else et donc i sera égal à 0. Donc en faites c'est comme si tu faisais des opérations élémentaires non? Donc c'est O(1)?

m dépend de t.length mais on fait quand même des opérations basiques, donc à part O(1) je vois pas

**WhiteCrow** · 09/12/2020, 23h45

Envoyé par antares56

Pour la 2 si j'essaye avec le t = {10,20,30};
i = 2
donc le while est valide on passe au if
si t[2] > = 0 && t[2]<t.length) donc le if n'est pas valide car t[2] n'est pas plus grand que t.length
ensuite on va direct dans le else et donc i sera égal à 0. Donc en faites c'est comme si tu faisais des opérations élémentaires non? Donc c'est O(1)?

Et avec les autres tableaux ?

Envoyé par antares56

m dépend de t.length mais on fait quand même des opérations basiques, donc à part O(1) je vois pas

Est-ce qu'avec un tableau deux fois plus grand l'exécution prendra plus ou moins de temps ?

**antares56** · 09/12/2020, 23h53

Envoyé par WhiteCrow

Et avec les autres tableaux ?

pour t{0} il se passe absolument rien et pour t={5,4,3,2,1,0};:
donc i = 5;
le while est bon donc passe à la boucle suivante:
le if est bon donc on passe à la boucle suivante
donc i prend la valeur t[5] donc i = 0;
et le programme finit ici

Est-ce qu'avec un tableau deux fois plus grand l'exécution prendra plus ou moins de temps ?

Plus de temps puisqu'il y aura plus de divisions à faire

**WhiteCrow** · 09/12/2020, 23h58

Envoyé par antares56

pour t{0} il se passe absolument rien et pour t={5,4,3,2,1,0};:
donc i = 5;
le while est bon donc passe à la boucle suivante:
le if est bon donc on passe à la boucle suivante
donc i prend la valeur t[5] donc i = 0;
et le programme finit ici

Et un tableau du genre t[]={0,1} ?

Envoyé par antares56

Plus de temps puisqu'il y aura plus de divisions à faire

Tu es donc en train de me dire que le temps n'est pas constant … donc que la complexité n'est pas en O(1) …

**antares56** · 10/12/2020, 00h02

Envoyé par WhiteCrow

Et un tableau du genre t[]={0,1} ?

i=1;
le while est bon
if est bon aussi
du coup i = 1
du coup ça tourne en boucle

Tu es donc en train de me dire que le temps n'est pas constant … donc que la complexité n'est pas en O(1) …[/QUOTE]

Ok donc étant donné que plus le tableau est grand plus il y a de divisions, c'est en log2(n)?

**WhiteCrow** · 10/12/2020, 00h12

Envoyé par antares56

i=1;
le while est bon
if est bon aussi
du coup i = 1
du coup ça tourne en boucle

Oui, par définition un algorithme doit toujours finir en un nombre fini d'étapes. Ce qui n'est pas le cas ici, il ne s'agit pas d'un algorithme, tu ne peux donc pas en déterminer la compléxité (qui ne dépend pas de la taille de l'entrée mais du contenu de l'entrée ce qui est très différent).

Envoyé par antares56

Tu es donc en train de me dire que le temps n'est pas constant … donc que la complexité n'est pas en O(1) …

Ok donc étant donné que plus le tableau est grand plus il y a de divisions, c'est en log2(n)?[/QUOTE]

Je sais pas ... comment peux-tu le prouver ?

**antares56** · 10/12/2020, 00h41

Envoyé par WhiteCrow

Oui, par définition un algorithme doit toujours finir en un nombre fini d'étapes. Ce qui n'est pas le cas ici, il ne s'agit pas d'un algorithme, tu ne peux donc pas en déterminer la compléxité (qui ne dépend pas de la taille de l'entrée mais du contenu de l'entrée ce qui est très différent).

Ok donc étant donné que plus le tableau est grand plus il y a de divisions, c'est en log2(n)?

Je sais pas ... comment peux-tu le prouver ?[/QUOTE]

Parce que quand c'est logarithmique on peut voir grâce au graphe que la courbe n'augmente pas considérablement comme une constante ou en quadratique par exemple

**Flodelarab** · 10/12/2020, 12h03

Arrêtez le carnage. antares56, tu ne trouves pas, car tu ne sais pas ce que tu cherches. C'est quoi la complexité algorithmique ? C'est essayer de répondre à la question "Si j'ai plus de clients, ai-je plus de travail pour les satisfaire ?". Si tu es coiffeur, oui. Ton travail de coiffeur augmente proportionnellement à ton nombre de clients. Mais si tu acteur de théâtre, non. Tu joues le même texte, une seule fois, que tu aies 20 spectateurs ou 150 spectateurs. La complexité du coiffeur est O(n) et celle de l'acteur O(1). On peut donc avoir pour complexité 1, n, n², n³, n⁴, etc, ln(n), exp(n) et leurs composés. Le critère important est la croissance comparée. Car tu peux très bien trouver une parabole (n²) qui passe par-dessus une exponentielle. 3n²+6 > 2exp(n) si n=0. Mais si n augmente, à l'infini, l'exponentielle sera toujours au dessus de ta parabole. Voilà pourquoi on dit que l'exponentielle croît plus vite qu'un polynôme.

Maintenant, dans tes bouts de code, si ton tableau en entrée est 10 fois plus grand, le travail sera-t-il 10 fois plus long ? 100 fois plus long ? 1000 fois plus long ? Constant ? Quelle est la formule en fonction de n ?

Note : la proportionnalité n'est pas obligatoire. Si, pour chaque client, tu donnes les coordonnées de tous les autres clients, tu auras n*n=n² opérations. Car pour chaque clients (n contextes), tu devras rechercher les coordonnées de chaque client (n opérations).

**antares56** · 10/12/2020, 17h24

Merci pour ta réponse déjà, mais par contre j'ai été clair dès le début, j'ai été transparent sur le fait que je n'avais pas la technique et que justement je suis venu ici pour que l'on m'explique le fonctionnement ,(ce que WhiteCrow a fait avec ses mots et je l'en remercie), y'a t'il une sorte de cours sur ce site sur la complexité? (je suis assez nouveau ici je sais pas trop où chercher )