Analyser des algorithmes pour la complexité temporelle

Question

J'analyse un algorithme et je veux juste savoir si je suis sur la bonne voie.

Pour cet algorithme, je ne compte que les multiplications sur la ligne qui ont *** en eux.

est ici l'algorithme:

1. Je suis donc à partir de la ligne la plus intérieure, je peux voir, il y a là 2 opérations (les deux multiplications).
2. Maintenant, je regarde les 2 boucles les plus internes, donc je peux dire que le p=p*20*z est exécuté exactement (j) + (j-1)+(j-2)+(j-3)...1 fois. Cela arrive à être égal à j(j+1)/2. Donc, au total, puisqu'il y a deux multiplications, cela arrive 2 * (j(j+1)/2).
3. Ensuite, la boucle "i" arrive exactement n fois, donc, au total, c'est n(2 * (n(n+1)/2)).

C'est mon processus de réflexion derrière cela. Ai-je raison? Merci.

Answer 1

Votre processus de réflexion est correct. Vous devez remplacer le terme j par un n (n étant la plus grande valeur que j peut supposer), mais c'est probablement une faute de frappe.

De plus, vous pouvez simplifier davantage d'où vous êtes:

n(2*(n(n+1)/2)) 
2*n*(n^2+n)/2 
n^3+n^2 

=> O(n^3) 

La dernière étape est parce que le terme n cubed va croître à un rythme beaucoup plus grand que le n carré terme, nous pouvons dire qu'il dominera le runtime pour grand n. Un autre point que je voudrais mentionner est que vous devriez peut-être considérer le magasin comme une opération ainsi que comme la multiplication à deux, bien que cela ne change évidemment pas l'exécution simplifiée de big-o.

Answer 2

calcul dans cet exemple pourrait être simplifiée si vous pouvez savoir que les trois boucles a la même condition de sortie up to n:

1. i <= n
2. j <= n
3. k <= j

Fondamentalement la troisième boucle exécuterait également n itérations car j <= n donc k <= n, cela signifie que la complexité serait n * n * n = O(n^3)

Answer 3

Voici comment vous pouvez obtenir l'ordre de croissance de votre algorithme méthodiquement: