0
Je cours en ligne sur les algorithmes et j'ai eu le quiz suivant. Je me suis trompé et j'essaie de comprendre la raison de la réponse.Complexité de l'algorithme et grande notation O
Lequel des éléments suivants est O (n^3)?
a) 11n + 151 + 100 gn
b) 1/3 n^2
c) 25 000 n^3
d) Toutes ces réponses.
La bonne réponse est (d) tout ce qui précède. La raison en est que la notation Big-O ne fournit que la limite supérieure du taux de croissance de la fonction lorsque n devient grand.
Je ne sais pas pourquoi la réponse n'est pas (c). Par exemple, la borne supérieure de (b) est inférieure à n^3.
Si quelque chose est O (n^2), il est aussi O (n^3). – Lee
La limite supérieure ne signifie pas nécessairement la limite * la plus stricte *. – SomeWittyUsername
Il n'y a pas de limite supérieure. Il y a beaucoup de limites supérieures. La notation Big-O spécifie ** une ** limite supérieure. Une notation associée fournit * la limite supérieure *, mais ce n'est pas la notation Big-O. –