1) Réorganiser l'efficacité suivante du plus petit au plus grand:
2^n, n!, n^5, 10000, nlog2(n)Quelques questions sur la complexité
Mon ans-> 10000 < nlog2 (n) < n^5 < 2^n < n!
Correct?
2) Efficacité d'un algo. est n^3, si un pas dans cet algo. prend 1 nanosec. (10^-9 secondes). Combien de temps cela prend-il à l'algo? traiter une entrée de taille 1000?
Je ne sais pas ... Est-ce (1000)^3 * 10^-9?
Question une est bonne. Question 2, je suppose que votre réponse est ce qu'ils recherchent, mais si par n^3 vous voulez dire O (n^3), vous ne pouvez pas y répondre (à moins que ce soit une utilisation de "l'efficacité algorithmique" I je ne suis pas familier avec).
La complexité Big-O donne une limite asymptotique au comportement de l'algorithme. On sait, pour "grand" n, que O (n^3) est plus grand que le temps nécessaire pour exécuter l'algorithme sur l'entrée de taille n. Notez les deux mises en garde - "grand n" et "limite asymptotique". Il n'y a rien pour empêcher une entrée de taille 1000 de prendre deux fois plus de temps qu'une entrée de taille 2000, tant qu'il existe des m tels que pour tout n> m, n^3 limite le temps d'exécution. De plus, rien n'empêche l'algorithme de prendre 1 nanoseconde sur chaque entrée, car n^3 est toujours lié à l'exécution - c'est juste très pessimiste.
C'est pourquoi la notation O grand est souvent d'utilisation limitée dans des situations pratiques. Il donne une vue d'ensemble du «pire des cas», mais ne décrit aucun scénario d'utilisation donné. Pour un ensemble de classes de complexité plus pratique (mais souvent négligé), google pour "Big theta".
Dans la définition de big-O, le facteur d'échelle est également important; il serait techniquement plus correct de dire "tant qu'il existe des constantes * m * et * k * telles que pour tout * n *> * m *, * k n * ³ limite le temps d'exécution." Big-thêta est génial, mais je ne pense pas que l'utilisation pratique de big-O est limitée par le fait qu'il est généralement utilisé pour se référer à une limite serrée, même si elle ne l'exige pas strictement. C'est plus facile, et parfois les maths sur un vrai lien thêta sont trop poilus pour en valoir la peine. – jtb
bon point, # 2 est techniquement impossible à répondre à partir de l'information donnée, bien que je suppose que les auteurs de la question voulaient juste la réponse qu'il a fournie. : -/ – Kip
Oui, il y a un facteur d'échelle - je l'ai omis délibérément, pour éviter encore plus de confusion pour le questionneur, mais merci de le mentionner :) –
Les deux réponses sont correctes
1) Oui, c'est correct.
2) C'est également correct. Analyse dimensionnelle: (1000^3 étapes) * 10^(- 9) secondes/étape
Si ce sont des devoirs, ce sont des questions terribles. –
vos deux réponses sont correctes. –