Sommando un array e notazione O-grande

Question

Come trovare un algoritmo per il calcolo del valore della somma nella matrice ??

Is è qualcosa di simile?

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

E come posso riferire con il tempo di esecuzione dell'algoritmo utilizzando notazione O

Questa è l'esame l'anno passato e ho bisogno di fare la revisione per il mio esame.

Domanda
Un array A [] tiene valore n intero è dato
1.Give un algoritmo per il calcolo della somma di tutti i valori nella matrice
2.Find il migliore e più semplice notazione O per il tempo di esecuzione dell'algoritmo.

Answer 1

Il problema è quello di trovare il somma di tutti i valori in modo da scorrere ogni elemento dell'array e aggiungere ogni elemento per un valore di somma provvisoria.

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

Dal momento che è necessario passare attraverso tutti gli elementi dell'array, questo programma dipende linearmente al numero di elementi . Se si dispone di 10 elementi, scorrere 10 elementi, se si dispone di un milione di avere altra scelta che quella di passare attraverso tutti i milioni di elementi e aggiungere ciascuno di essi. Così il tempo la complessità è Θ (n) .

Se si sta trovando la somma di tutti gli elementi e non si sa nulla circa i dati allora avete bisogno di guardare tutti gli elementi almeno una volta. Così n è il limite inferiore. Inoltre, non è necessario guardare l'elemento più di una volta. n è il limite superiore. Da qui la complessità è Θ (n).

Tuttavia, se si sa qualcosa circa l'elements..say si ottiene un Sequency dei numeri naturali n, si può fare in tempo costante con n (n + 1) / 2. Se i dati che si ottiene sono casuali, allora non hai scelta, ma fare l'algoritmo di tempo sopra lineare.

Answer 2

Da n è la dimensione della matrice e tutto quello che dovete fare è iterare da begeinning per terminare la notazione O-grande è O [n]

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

Answer 3

Credo che si intende "mentre j <= N", è necessario specificare questo.

Il tempo di esecuzione deve essere O (n), penso che, quando si dispone di un solo ciclo.

Answer 4

Per calcolare O per questo algoritmo è necessario contare il numero di volte in cui ogni riga di codice viene eseguito. In seguito si avrà solo contare le operazioni fondamentali, ma iniziare a contare tutti.

Quindi, quante volte sarà la j: = 1 riga correre? Quante volte sarà la somma: = 0 run? Quante volte sarà la condizione del ciclo while eseguire? Le istruzioni all'interno del ciclo while?

Sommare questi tutto. Si noterà che il valore che si ottiene sarà qualcosa di simile a 1 + 1 + n + n + n = 2 + 3n. in tal modo si può concludere che si tratta di una funzione lineare su n.