Complexité informatique

[Sarapproche]

Bonjour

Il y a un truc que je ne comprends pas dans les qcms sur la complexité en informatique (ceux donnés sur moodle) 

 

Dans le 1er item, je trouve que  le programme 1 fait 500 fois plus d'itérations que le 2, or l'item est vrai pour 100 fois plus  (prog1 : 1000 * 500 et prog2 1000)

https://image.noelshack.com/fichiers/2021/08/5/1614331852-info5.png

 

Dans les autres items pourtant mon raisonnement marchait, mais du coup j'ai peur que ce soit un coup de chance haha et que j'ai pas du tout la bonne méthode  ! 

dans l'item 2 par exemple je trouve prog1 = 1000*(500+500) et dans prog2=1000*500 donc 2 fois plus (item faux)

https://image.noelshack.com/fichiers/2021/08/5/1614331919-info6.png

 

dans l'item3 prog1 1000*1000 et prog2= 1000*1000 donc pareil (item faux) 

https://image.noelshack.com/fichiers/2021/08/5/1614331970-info7.png

 

dans l'item4 prog1=1000*500*250 et prog2=1000*(1000+1000) (item faux)

https://image.noelshack.com/fichiers/2021/08/5/1614332015-info8.png

 

désolée pour ce long message ! mais si une personne peut m'expliquer comment elle a fait pour le 1er item ce serait super  

 

merci d'avance !

et bonne fin de week-end  

[Sans-Visage]

Hey !

 

- plus de 100 fois plus (je me suis fait avoir aussi)

 

- t'as les bonnes valeurs donc oui probablement le bon raisonnement ^^

 

- ouep !

 

- moi j'ai 1000*1000*1000 et 1000+1000+1000 

 

Dis moi si t'as besoin de plus de détails  

[Shrex]

il y a 7 minutes, DuTACKauTac a dit :

plus de

c'était donc ça... (je comprenais pas pourquoi c'était juste alors que mon raisonnement marchait sur le reste, Merci du coup !!)

Edited March 2, 2021 by Shrex

[Sans-Visage]

il y a 7 minutes, Shrex a dit :

c'était donc ça... (je comprenais pas pourquoi c'était juste alors que mon raisonnement marchait sur le reste, Merci du coup !!)

 

ça me rassure TELLEMENT de voir que je suis pas le seul !! Alors que genre la consigne c'est la même à chaque exo hein !! Mais non mon cerveau vraiment il a sauté ces deux mots quatre fois de suite !!!!

[Odontoboulot]

autant pour les exos avec des chiffre entre les () c'est assez rapide d'y répondre, mais c'est quoi votre méthode quand y'a des pos1 pos2 etc ? 

parce que si j'essaie de le faire de tête j'ai faux à ^{plus de} 100%, et si je fais méthode papier ça prend un peu de temps 

[Sans-Visage]

il y a 55 minutes, Soul a dit :

mais c'est quoi votre méthode quand y'a des pos1 pos2 etc ? 

 

Le premier pos vit sa vie 

Le deuxième pos va avoir n(n+1)/2 itérations (somme des entiers de 1 à n)

Et on multiplie les deux (tu peux arrondir, les profs ont pas l'air de demander des calculs à l'itération près)

Edited March 2, 2021 by DuTACKauTac

[Odontoboulot]

il y a 18 minutes, DuTACKauTac a dit :

 

Le premier pos vit sa vie 

Le deuxième pos va avoir n(n+1)/2 itérations (somme des entiers de 1 à n)

Et on multiplie les deux (tu peux arrondir, les profs ont pas l'air de demander des calculs à l'itération près)

 

franchement désolé, je vois pas bien d'où sort la formule, mais du coup le programme 2 fait exactement la même chose donc on lui applique la formule aussi ?

 

[MrPouple]

Salut !

 

il y a 15 minutes, Soul a dit :

franchement désolé, je vois pas bien d'où sort la formule

De là :

N'hésite pas si tu ne comprends toujours pas

 

Au plaisir,

 

il y a 44 minutes, DuTACKauTac a dit :

 

Le premier pos vit sa vie 

Le deuxième pos va avoir n(n+1)/2 itérations (somme des entiers de 1 à n)

Et on multiplie les deux (tu peux arrondir, les profs ont pas l'air de demander des calculs à l'itération près)

Alors par contre si on parle toujours du même problème avec pos1 entre 0 et 999 et pos2 entre 0 et pos1 c'est pas ça. Tu multiplies pas les deux dans ce cas vu que tu le fais déjà en considérant que pos2 va de 0 à pos1.

[Odontoboulot]

il y a 2 minutes, MrPouple a dit :

Salut !

 

De là :

N'hésite pas si tu ne comprends toujours pas

 

Au plaisir,

 

 

Salut,

 

mais justement, cette formule je pense pas l'avoir vu ailleurs, sans elle concrètement comment on procède ? 

[Sans-Visage]

il y a 5 minutes, MrPouple a dit :

Alors par contre si on parle toujours du même problème avec pos1 entre 0 et 999 et pos2 entre 0 et pos1 c'est pas ça. Tu multiplies pas les deux dans ce cas vu que tu le fais déjà en considérant que pos2 va de 0 à pos1.

Oooooops oui mon cerveau s'est embrouillé merci !

 

il y a 1 minute, Soul a dit :

mais justement, cette formule je pense pas l'avoir vu ailleurs, sans elle concrètement comment on procède ? 

Bah du coup je me suis embrouillé avec le truc que la prof a proposé sur moodle :

On prend la valeur moyenne de la deuxième boucle (pos2, donc 500) et cette fois on multiplie avec la première (ce qui donne 500 000)

Au fait c'est la même chose que la formule mais appliquée différemment 

En gros elle essaie de dire que pos2 sur la totalité des itérations, vaudra en moyenne 500 (on aura en moyenne 500 itérations de pos2, comme il va de 0 à 999), et comme on a 1000 itérations de pos1 on va multiplier les deux 

[Pitchounou]

Le 28/02/2021 à 18:33, Sarou a dit :

ans les autres items pourtant mon raisonnement marchait, mais du coup j'ai peur que ce soit un coup de chance haha et que j'ai pas du tout la bonne méthode  ! 

dans l'item 2 par exemple je trouve prog1 = 1000*(500+500) et dans prog2=1000*500 donc 2 fois plus (item faux)

https://image.noelshack.com/fichiers/2021/08/5/1614331919-info6.png

Salut salut, désolé de relancer le truc aussi mais autant j'ai compris tout le reste autant je comprends pas comment on trouve ça ? 

 

Edit : j'ai rien dit on est bon

Edited March 2, 2021 by Pitchounou

[MrPouple]

Ah ! Cette formule est assez connue, on l'apprend au lycée en général, c'est juste une astuce mathématique, en soit on en a pas besoin. Ce qu'il faut comprendre avant tout c'est que le nombre d'itérationz correspond à additioner les nombres de 1 à 999

il y a 1 minute, DuTACKauTac a dit :

Oooooops oui mon cerveau s'est embrouillé merci !

 

Bah du coup je me suis embrouillé avec le truc que la prof a proposé sur moodle :

On prend la valeur moyenne de la deuxième boucle (pos2, donc 500) et cette fois on multiplie avec la première (ce qui donne 500 000)

Au fait c'est la même chose que la formule mais appliquée différemment 

En gros elle essaie de dire que pos2 sur la totalité des itérations, vaudra en moyenne 500 (on aura en moyenne 500 itérations de pos2, comme il va de 0 à 999), et comme on a 1000 itérations de pos1 on va multiplier les deux 

Tkt aucun soucis haha Par contre le nombre d'itérations ici c'est pas 500000 mais 499500, elle le précise dans le cours ?

[Odontoboulot]

il y a 4 minutes, DuTACKauTac a dit :

Oooooops oui mon cerveau s'est embrouillé merci !

 

Bah du coup je me suis embrouillé avec le truc que la prof a proposé sur moodle :

On prend la valeur moyenne de la deuxième boucle (pos2, donc 500) et cette fois on multiplie avec la première (ce qui donne 500 000)

Au fait c'est la même chose que la formule mais appliquée différemment 

En gros elle essaie de dire que pos2 sur la totalité des itérations, vaudra en moyenne 500 (on aura en moyenne 500 itérations de pos2, comme il va de 0 à 999), et comme on a 1000 itérations de pos1 on va multiplier les deux 

 

il y a 3 minutes, MrPouple a dit :

Ah ! Cette formule est assez connue, on l'apprend au lycée en général, c'est juste une astuce mathématique, en soit on en a pas besoin. Ce qu'il faut comprendre avant tout c'est que le nombre d'itérationz correspond à additioner les nombres de 1 à 999

 

 

pour le coup je suis d'accord pos2 fera 1 + 2+ ...+ 999, ok, mais du coup comment on procède avec pos1, suffit bien de multiplier par 1000 ?

[Sans-Visage]

il y a 11 minutes, MrPouple a dit :

le cours ?

Le cours ?  [Edit Pouple : héhé pas de pb si pas de cours]

Du coup non c'est juste une réponse qu'elle a mis à une question sur moodle (où elle avait fait cet arrondi), et comme je l'avais dit tout à l'heure ils ont pas l'air d'attendre des réponses précises, tant qu'on comprend que c'est "plus de 100 fois supérieur" ça a l'air ok 

 

il y a 11 minutes, Pitchounou a dit :

Salut salut, désolé de relancer le truc aussi mais autant j'ai compris tout le reste autant je comprends pas comment on trouve ça ? 

Alooors dans le deuxième programme on va avoir le même cas, on répète 1000 fois une boucle qui aura pour valeur moyenne 500. Dans le deuxième cas (premier programme), on fait ça mais avec deux boucles, donc au final on aura (seulement) deux fois plus d'itérations ! par contre, on aura bien le même résultat

 

il y a 4 minutes, Soul a dit :

pour le coup je suis d'accord pos2 fera 1 + 2+ ...+ 999, ok, mais du coup comment on procède avec pos1, suffit bien de multiplier par 1000 ?

Si tu fais l'addition 1+2+3+...+999 tu trouves bien le nombre d'itérations totales ! Parce que c'est précisément le nombre de fois que le tout se répète 

Par contre, si tu réfléchis avec la valeur moyenne de pos2 (~500), il va bien falloir répéter pos1 fois la valeur moyenne de pos2

[Pitchounou]

il y a 2 minutes, DuTACKauTac a dit :

Si tu fais l'addition 1+2+3+...+999 tu trouves bien le nombre d'itérations totales !

Cette somme ça correspond pas seulement aux itérations de pos2 ? Pourtant quand le prof l'avait expliqué sur vidéo anagramme je crois de la semaine 6 ou 7 on avait une boucle avec pos1, et une boucle post2 qui allait de 0 à pos1, et quand il calculait la somme en utilisant n(n+1)/2 il disait que c'était simplement les itérations de la boucle imbriquée ducoup je suis PAU-MEE 

[Odontoboulot]

il y a 8 minutes, DuTACKauTac a dit :

Le cours ?  [Edit Pouple : héhé pas de pb si pas de cours]

Du coup non c'est juste une réponse qu'elle a mis à une question sur moodle (où elle avait fait cet arrondi), et comme je l'avais dit tout à l'heure ils ont pas l'air d'attendre des réponses précises, tant qu'on comprend que c'est "plus de 100 fois supérieur" ça a l'air ok 

 

Alooors dans le deuxième programme on va avoir le même cas, on répète 1000 fois une boucle qui aura pour valeur moyenne 500. Dans le deuxième cas (premier programme), on fait ça mais avec deux boucles, donc au final on aura (seulement) deux fois plus d'itérations ! par contre, on aura bien le même résultat

 

Si tu fais l'addition 1+2+3+...+999 tu trouves bien le nombre d'itérations totales ! Parce que c'est précisément le nombre de fois que le tout se répète 

Par contre, si tu réfléchis avec la valeur moyenne de pos2 (~500), il va bien falloir répéter pos1 fois la valeur moyenne de pos2

 

je comprend juste pas la notion de valeur moyenne, pourquoi on multiplie pos1 par 500 ?

vu qu'on fais pos2 (pos1)  il devrait faire lui aussi 1000 fois cette répétition non ?

[Sans-Visage]

il y a 3 minutes, Pitchounou a dit :

Cette somme ça correspond pas seulement aux itérations de pos2 ? Pourtant quand le prof l'avait expliqué sur vidéo anagramme je crois de la semaine 6 ou 7 on avait une boucle avec pos1, et une boucle post2 qui allait de 0 à pos1, et quand il calculait la somme en utilisant n(n+1)/2 il disait que c'était simplement les itérations de la boucle imbriquée ducoup je suis PAU-MEE 

 

Alooors en vrai je te conseille la technique de Paola, genre tu réfléchis juste à la valeur moyenne que prendra le pos2 et tu le répètes pos1 fois, je trouve ça beaucoup plus clair !

 

Sinon on peut prendre l'exemple avec 5 :

pos1 ; pos2 in range() ; nbtotal

0 ; 0 ; 0

1 ; 0 ; 1

2 ; 1 ; 3

3 ; 2 ; 6

4 ; 3 ; 10

5 ; 4 ; 15

 

Et tu vois bien à droite que le nombre d'itérations totales est 1+2+...+n ^^ 

(À chaque fois, le pos1 rajoute une itération, par contre à chaque fois le pos2 réalise autant d'itérations que la valeur qui lui est associée)

 

 

il y a 12 minutes, DuTACKauTac a dit :

[Edit Pouple : héhé pas de pb si pas de cours]

ATTENDS QUE-HEIN QUOI ??? @MrPouple de quel droit tu fais ça ??

 

il y a 3 minutes, Soul a dit :

je comprend juste pas la notion de valeur moyenne, pourquoi on multiplie pos1 par 500 ?

vu qu'on fais pos2 (pos1)  il devrait faire lui aussi 1000 fois cette répétition non ?

Pos2 sera dans la range de Pos1 (regarde l'exemple au dessus avec 5) 

Donc si pos1 = 766, on aura pos2 in range(765)

Ca va être ça pour toutes les valeurs de Pos1 de 0 à 999, ça veut dire que pos2 sera en moyenne in range(500)

[Odontoboulot]

il y a 17 minutes, DuTACKauTac a dit :

 

Pos2 sera dans la range de Pos1 (regarde l'exemple au dessus avec 5) 

Donc si pos1 = 766, on aura pos2 in range(765)

Ca va être ça pour toutes les valeurs de Pos1 de 0 à 999, ça veut dire que pos2 sera en moyenne in range(500)

j'abandonne, Merci quand même 

[Vaiana]

à l’instant, Soul a dit :

j'abandonne, Merci quand même 

 

je sens que j'vais pleurer quand je vais entamer les qcm

[Sarapproche]

@DuTACKauTac 

Il y a 2 heures, DuTACKauTac a dit :

plus de 100 fois plus (je me suis fait avoir aussi)

ah noooon le piège trop nul !!! merci !!!!

 

@Pitchounou désolée j'arrive après la bataille ! la prof assez bien expliqué sur moodle si jamais c'est toujours pas clair avec les réponses si dessus dis moi !  

[MrPouple]

il y a 52 minutes, DuTACKauTac a dit :

ATTENDS QUE-HEIN QUOI ??? @MrPouple de quel droit tu fais ça ??

Ahah privilège d'ancien webi, c'est moi qui ai mis en ligne cette version du forum, il y en avait une autre avant 2017  

[Linou]

@DuTACKauTac

Holaaa, en gros j'avais calculé comme un suite aussi, mais c'est bien plus facile de faire comme tu fais : si j'ai bien compris t'auras environ 500 tours où pos 2 fera moins de 500 itérations et 500 tours où pos 2 fera plus de 500 itérations ? Du coup on dis qu'en moyenne pos 2 fait 500 itérations, on multiplie 500 par 1000 et basta?

Si j'ai rien compris je veux bien des explications

[MrPouple]

il y a 5 minutes, Alpassino a dit :

@DuTACKauTac

Holaaa, en gros j'avais calculé comme un suite aussi, mais c'est bien plus facile de faire comme tu fais : si j'ai bien compris t'auras environ 500 tours où pos 2 fera moins de 500 itérations et 500 tours où pos 2 fera plus de 500 itérations ? Du coup on dis qu'en moyenne pos 2 fait 500 itérations, on multiplie 500 par 1000 et basta?

Si j'ai rien compris je veux bien des explications

Non non t'as bien compris c'est exactement ça  

[Sarapproche]

@Alpassino alors je t'avoue que je comprends pas le pourquoi du comment mais oui  j'ai suivi ce raisonnement et ça a marché mdr 

[MrPouple]

On peut même avoir le nombre exact d'itérations avec ce raisonnement là. Puisqu'en réalité pos1 variera entre 0 et 999. Il aura donc en moyenne une valeur de 499.5 ce qui donne 49500 itérations, le nombre exact