Impossible de comprendre le temps d'exécution dans un algorithme

Question

J'ai du mal à déterminer le temps d'exécution de chaque étape d'un algorithme. Je ne peux pas comprendre la logique. Nous connaissons tous avant de déterminer le Big O ou Thêta dans un algorithme, nous devons calculer le temps d'exécution de chaque étape, puis nous calculons l'ordre en fonction du temps d'exécution.

Je trouve plus facile de calculer la commande que le Big O ou le Theta, mais mon problème est de calculer le temps d'exécution.

Exemple:

for i=0 to **n** 

dothisStep 

Le temps d'exécution de la présente est la suivante: (n + 1) qui en fait un ordre de O (N) - ce qui est facile et je compris pourquoi-- mon problème est avec les "plus durs". Parfois, je suis censé obtenir n (n + 1)/2, parfois n (n + 1), mais je ne peux pas comprendre comment ou pourquoi! Quelles sont les règles?

Answer 1

Je pense que quelque chose qui vous aidera ici lorsque vous faites ces problèmes est de penser à ce qui se passe comme n approche l'infini. Dans l'exemple de n + 1, ce + 1 devient très insignifiant par rapport à n.

Votre autre exemple: n(n+1) - Encore une fois, l'ajout de 1 lorsque n approche l'infini est très insignifiant, donc nous laissons tomber le + 1. Cela laisse n(n) qui est n^2.