Qu'est-ce que la notation d'ordre f (n) = O (g (n))?

Question

Question 1: Dans quelles circonstances O(f(n)) = O(k f(n)) serait la forme d'analyse de complexité temporelle la plus appropriée?

Question 2: travail de définition mathématique de O notation, comment montrer que O(f(n)) = O(k f(n)), pour k positive constante?

Pour la première question, je pense que c'est la forme moyenne et la pire des cas de complexité temporelle. Ai-je raison? Et que devrais-je écrire d'autre?

Pour la deuxième question, je pense que nous devons définir la fonction mathématiquement. Donc, la réponse est-elle quelque chose comme la multiplication par une constante correspond juste à un réajustement de la valeur de la constante arbitraire k dans la définition de O?

Answer 1

La question 1 est un peu vague, mais votre réponse à la question 2 fait définitivement défaut. La question dit "travailler à partir de la définition mathématique de la notation O". Cela signifie que votre instructeur vous veut utiliser la mathématique définition:

f (x) = O (g (x)) si et seulement si la limite [x -> a +] | f (x)/g (x) | < l'infini, pour certains une

Et il veut que vous brancher g (x) = k f (x) et prouver que cette inégalité est. L'argument général que vous avez publié pourrait vous donner un crédit partiel, mais c'est un raisonnement plutôt que des mathématiques, et la question demande des mathématiques.

Answer 2

Mon point de vue: Pour le premier, je pense qu'il est moyen et le pire forme de cas de temps complexité. ai-je raison? et qu'est-ce que j'écris d'autre dans ça?

Non! La notation Big O n'a rien à voir avec le cas moyen ou le pire des cas. Il s'agit seulement de l'ordre de croissance d'une fonction - en particulier, à quelle vitesse une fonction se développe par rapport à une autre. Une fonction f peut être O(n) dans le cas moyen et O(n^2) dans le pire des cas - cela signifie que la fonction se comporte différemment en fonction de ses entrées, et donc les deux cas doivent être comptabilisés séparément.

En ce qui concerne la question 2, il est évident pour moi du libellé de la question que vous devez commencer par la définition mathématique de Big O. Par souci de l'exhaustivité, il est:

Définition formelle: f (n) = O (g (n)) signifie qu'il y a des constantes positives c et k, telles que 0 ≤ f (n) ≤ cg (n) pour tout n ≥ k. Les valeurs de c et k doivent être fixées pour la fonction f et doivent ne pas dépendre de n.

(source de http://www.itl.nist.gov/div897/sqg/dads/HTML/bigOnotation.html)

Donc, vous devez travailler à partir de cette définition et écrire une preuve mathématique montrant que f(n) = O(k(n)).Commencez par remplacer O(g(n)) par O(k*f(n)) dans la définition ci-dessus; le reste devrait être assez facile.