Comparaison complexité algorithmes
Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
-
Youfo
- Messages: 3
- Enregistré le: 16 Déc 2016, 16:33
-
par Youfo » 07 Mar 2019, 19:16
Bonjour,
Je suis bloqué sur un exercice qui pourrait pourtant sembler basique, mais je ne sais pas comment m'y prendre
. Si vous auriez quelques pistes à me donner pour me guider dans ma réflexion, ce sera sans refus.
Voici le sujet et la question :
Pour résoudre un problème algorithmique, dont la variable d’entrée est notée n, on dispose de deux algorithmes :
ALGO-BOF dont la complexité en temps est de O(n2) et ALGO-TOP dont la complexité en temps est de O(n log n).
— ALGO-BOF est codé par un super programmeur qui garantit que le programme fait exactement 2n2 opérations
élémentaires, il le fait en plus tourner sur sa super machine, capable d’effectuer 20 000 000 000
d’opérations élémentaires par seconde.
— ALGO-TOP, quant-à-lui est codé par un programmeur moyen qui pense que le programme ne fait pas plus
de 50n log n opérations élémentaires et il le fait tourner en salle TP tout en regardant YouTube, sa machine
n’effectuant alors que 1 000 000 000 d’opérations élémentaires par seconde.
À partir de quelle valeur de n le programme codant ALGO-TOP est-il plus rapide que celui codant ALGO-BOF ?
Merci en avance
-
tournesol
- Membre Irrationnel
- Messages: 1509
- Enregistré le: 01 Mar 2019, 19:31
-
par tournesol » 07 Mar 2019, 19:56
Temps d'execution d'algotop :50nlogn/10^9
etc
tu obtiens l'inequation logn/n <2 x 10^(-3) que tu resous avec une calculette .
ATTENTION log désigne le logarithme décimal .
-
mathelot
- Habitué(e)
- Messages: 13687
- Enregistré le: 08 Juin 2006, 08:55
-
par mathelot » 07 Mar 2019, 20:24
La mise en équation n'est pas difficile:
}{10^9} < \dfrac{n^2}{10^{10}}})
soit
} > 500)
après on écrit un programme.
n vaut 1603
-
Youfo
- Messages: 3
- Enregistré le: 16 Déc 2016, 16:33
-
par Youfo » 07 Mar 2019, 21:23
mathelot a écrit:La mise en équation n'est pas difficile:
soit
après on écrit un programme.
n vaut 1603
Merci beaucoup, j'ai compris.. La solution était juste devant moi, mais j'ai paniqué
Mais comment trouvez vous le resultat final (1603) ?
Modifié en dernier par
Youfo le 07 Mar 2019, 21:34, modifié 1 fois.
-
Youfo
- Messages: 3
- Enregistré le: 16 Déc 2016, 16:33
-
par Youfo » 07 Mar 2019, 21:27
tournesol a écrit:Temps d'execution d'algotop :50nlogn/10^9
etc
tu obtiens l'inequation logn/n <2 x 10^(-3) que tu resous avec une calculette .
ATTENTION log désigne le logarithme décimal .
Merci, mais je trouve au final la meme inéquation que "mathelot", c'est à dire : n/log(n)>500
-
mathelot
- Habitué(e)
- Messages: 13687
- Enregistré le: 08 Juin 2006, 08:55
-
par mathelot » 07 Mar 2019, 21:59
Youfo a écrit:Mais comment trouvez vous le resultat final (1603) ?
j'ai fait un programme qui calcule n/log(n) pour n variant de 1 à 2500 avec un pas de 100
puis n variant de 1600 à 1700 avec un pas de 1
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 82 invités
