Sommer un tableau et Big O notation

Question

Comment trouver un algorithme de calcul de la valeur de somme dans le tableau ??

Is est quelque chose comme ça?

Algorithm Array Sum
Input: nonnegative integer N, and array A[1],A[2],...,A[N]
Output: sum of the N integers in array A
Algorith Body:
j:=1
sum:=0
while j<N
      sum := sum + a[J]
      j:=j+1
  end while
end Algorithm Array Sum

Et comment je peux le relier avec le temps d'exécution de l'algorithme en utilisant la notation O

Ceci est l'examen de la dernière année et je dois faire une révision pour mon examen.

Question
Un tableau A [] de maintien de valeur entière de n est donnée
1.Give un algorithme pour calculer la somme de toute la valeur du tableau
2.Find la plus simple et la meilleure notation O pour le temps d'exécution de l'algorithme.

Answer 1

La question est de trouver le somme de toutes les valeurs pour itérer à travers chaque élément du tableau et ajouter chaque élément à une valeur de somme temporaire.

temp_sum = 0
for i in 1 ...array.length
    temp_sum = temp_sum + array[i]

Puisque vous devez passer par tous les éléments du tableau, ce programme dépend linéairement du nombre d'éléments . Si vous avez 10 éléments, 10 éléments itérer, si vous avez un million vous avez pas d'autre choix que de passer par tous les millions d'éléments et ajouter chacun d'eux. Ainsi, le complexité temporelle est Θ (n) .

Si vous trouvez la somme de tous les éléments et vous ne savez rien sur les données alors vous devez regarder tous les éléments au moins une fois. Ainsi n est le limiteinf. Vous devez également regarder pas l'élément plus d'une fois. n est la limite supérieure. D'où la complexité est Θ (n).

Toutefois, si vous savez quelque chose sur le elements..say vous obtenez un Sequency de n nombres naturels, vous pouvez le faire en temps constant avec n (n + 1) / 2. Si les données que vous obtenez sont aléatoires que vous avez pas d'autre choix, mais ne l'algorithme linéaire ci-dessus.

Answer 2

Depuis n est la taille du tableau et tout ce que vous avez à faire est itérer du début à la fin de la notation Big O est O [n]

integer N= Size_array;
array a[N]
j=1 
sum=0
while j<=N 
 sum += a[j]  
 j++
end while

Answer 3

Je pense que vous vouliez dire "tandis que j <= N", vous devez spécifier.

Le temps d'exécution est O (n), je pense, que vous avez une seule boucle.

Answer 4

Pour calculer O pour cet algorithme, vous devez compter le nombre de fois que chaque ligne de code est exécuté. Plus tard, vous ne compter les opérations de base, mais commencer en comptant tous.

Alors, combien de fois le j: = 1 ligne courir? Combien de fois la somme: = 0 run? Combien de fois l'état de la boucle while exécuter? Les instructions contenues dans la boucle while?

Somme ces tout. Vous remarquerez que la valeur que vous obtenez sera quelque chose comme 1 + 1 + n + n + n = 2 + 3n. ainsi vous pouvez en conclure qu'il est une fonction linéaire sur n.