de comptage des opérations primitives

Voici les opérations primitives j'envisage:de comptage des opérations primitives

Attribution d'une valeur à une variable
appel d'une méthode
Exécution d'une opération arithmétique
En comparant deux nombres
Suite une référence d'objet

J'ai une bonne compréhension de la façon de les compter pour une normale boucle comme ceci:

for (i=1; i<=n; i++) { ... }

Ce serait 4 + n + n * (nombre d'opérations primitives dans le corps en boucle), parce que nous avoir:

1 pour i initialisation comme une
n + 1 pour comparer i à n
2 pour i ++ car cela est juste i = i + 1, qui est à la fois une assignation et plus
Et puis nous répétons le corps n fois , D'où l'on multiplie par le corps n

Cependant, je suis coincé sur la façon de compter ceci:

for (i=0; i<n; i+2) { ... }

Pour les comparaisons, je pense que c'est 1+ceil(n/2), mais comment puis-je me débarrasser de la fonction ceil?

Pour les répétitions du corps, je pense floor((n+1)/2), mais je ne sais pas comment se débarrasser de la fonction de plancher.

Source

2017-07-08 Konrad

Vous pouvez juste environ avec n/2 et (n + 1)/2 pour toutes les fins du calcul de la complexité asymptotique et O (n) – frozen

Pourquoi voulez-vous vous débarrasser de ces fonctions? Ils décrivent avec précision votre nombre d'opérations. –

On me demande de donner le nombre d'opérations primitives. Cette boucle for est juste une petite section d'une méthode beaucoup plus grande et plus complexe. Si je n'avais pas les fonctions, je serais capable de tout multiplier, et de simplifier à une équation simple. – Konrad

Algorithm prefixAvg2(X): 
    input: An n-element array X 
    output: An n-element array A of numbers such that A[i] is the average of elements X[0], ..., X[i] 

1 Declare and initialize array A 
2 a = 0 
3 for i = 0 to n-1 do 
4 a += X[i] 
5 A[i] = a/(i+1) 
6 return array A

Source

2018-03-09 14:32:46 user9468116

de comptage des opérations primitives

Répondre

Questions connexes