Résumant un Tableau et la Notation Grand O

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

Est quelque Chose comme cela?

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 O-Notation

C'est la dernière année de l'examen et j'ai besoin de faire la révision de mon examen.

Question
Un Tableau A[] holding n entier dont la valeur est donnée
1.Donner un algorithme pour le calcul de la somme de la valeur dans le tableau
2.Trouver le plus simple et le plus S-notation pour le temps d'exécution de l'algorithme.

OriginalL'auteur | 2009-05-24

  1. 12

    La question est de trouver le somme de toutes les valeurs donc itérer sur chaque élément du tableau et ajouter chaque élément temporaire de la valeur de somme.

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

    Car vous avez besoin pour passer à travers tous les éléments dans le tableau, ce programme dépend linéairement du nombre d'éléments. Si vous avez 10 éléments, itérer sur 10 éléments, si vous avez un million vous n'avez pas d'autre choix que de passer par tous les millions d'éléments et d'ajouter chacun d'eux. Ainsi, le temps, la complexité est en Θ(n).

    Si vous êtes à la recherche de la somme de tous les éléments et vous ne savez pas quelque chose sur les données, alors vous devez examiner tous les éléments au moins une fois. Donc n est la limite inférieure. Vous avez aussi besoin de ne pas regarder l'élément plus d'une fois. n est aussi la limite supérieure. D'où la complexité est en Θ(n).

    Toutefois, si vous savez quelque chose sur les éléments..dire que 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, alors vous n'avez pas le choix, mais ne le ci-dessus, le temps linéaire de l'algorithme.

    +1 pour la mention de Θ(n).
    +1 pour la lecture de la question wrt pour les intrants mis à 1 au lieu de 0 basée.
    séquence de n nombres naturels...n(n+1)/2 je crois que tu voulais dire "séquence de n nombres naturels consécutifs" (bien que d'autres modèles peuvent également être fait en temps constant)

    OriginalL'auteur unj2

  2. 4

    Depuis n est la taille de la table et tout ce que vous avez à faire est d'effectuer une itération de begeinning à la fin de la notation Grand O est O[n]

    integer N= Size_array;
array a[N]
j=1 
sum=0
while j<=N 
 sum += a[j]  
 j++
end while
    +1 parce que quelqu'un downvoted ce parfaitement bien la réponse (??)
    ce n'est pas une réponse parfaite.
    -1 : Entrée: entier positif N, et le tableau A[1], [2],...,A[N] A[ 0 ] n'est pas défini.
    évidemment, je n'ai pas de comprendre comment non négatif serait interpet que le tableau n'est pas commencer à l'indice 0?
    la limite n'est pas serré.

    OriginalL'auteur TStamper

  3. 0

    Je pense que vous avez voulu dire ", alors que j <= N", vous devez spécifier ce.

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

    vous devez commencer à < a pas <=, si <= puis le programme va planter depuis tableau[j] lorsque j=n sera à l'extérieur des limites du terrain
    Non, le problème, affirme qu'il est indexé de 1 à N inclus. Ce n'est pas C. Entrée: entier positif N, et le tableau A[1], [2],...,A[N]

    OriginalL'auteur Valentin Rocher

  4. 0

    Pour calculer O pour cet algorithme, vous devez compter le nombre de fois que chaque ligne de code s'exécute. Plus tard, vous ne compter que les opérations fondamentales mais commencer par le comptage de tous.

    Donc, combien de fois le j := 1 ligne de courir? Combien de fois la somme := 0 courir?
    Combien de fois la boucle while condition de l'exécution? Les instructions à l'intérieur de la boucle while?

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

    OriginalL'auteur Vincent Ramdhanie