Sumando una matriz y la notación O grande

Question

¿Cómo encontrar un algoritmo para calcular el valor de la suma de la matriz ??

Es es algo como esto?

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

Y cómo puedo relacionarlo con el tiempo de ejecución del algoritmo mediante el uso de notación O

Este es el examen el año pasado y tengo que hacer la revisión para el examen.

Pregunta
Un Array A [] sosteniendo valor n número entero se da
1.Give un algoritmo para calcular la suma de todos los valores de la matriz
2.Find el más simple y mejor notación O por el tiempo de ejecución del algoritmo.

Answer 1

La cuestión es encontrar el suma de todos los valores para que iterar a través de cada elemento de la matriz y añadir cada elemento a un valor de la suma temporal.

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

Ya que se necesita para ir a través de todos los elementos de la matriz, este programa depende linealmente con el número de elementos . Si usted tiene 10 elementos, iterar a través de 10 elementos, si usted tiene un millón que no tienen otra opción que ir a través de todos los millones de elementos y añadir cada uno de ellos. Así, la complejidad de tiempo es Θ (n) .

Si usted está encontrando la suma de todos los elementos y usted no sabe nada acerca de los datos entonces usted necesita para buscar en todos los elementos al menos una vez. Por lo tanto n es el límite inferior. También es necesario mirar el elemento más de una vez. n es también el límite superior. Por lo tanto la complejidad es Θ (n).

Sin embargo, si usted sabe algo sobre el elements..say se obtiene una Secuencia de los números naturales n, puede hacerlo en un tiempo constante con n (n + 1) / 2. Si los datos que recibe son al azar, entonces no tienen más remedio que hacer el algoritmo de tiempo lineal anteriormente.

Answer 2

Desde n es el tamaño de la matriz y todo lo que tiene que hacer es iterar de principio a fin el la notación O grande es O [n]

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

Answer 3

Creo que significaba "mientras que j <= N", se necesita especificar esto.

El tiempo de ejecución será de O (n), creo que, como sólo tiene un bucle.

Answer 4

Para calcular O para este algoritmo necesita para contar el número de veces que cada línea de código se ejecuta. Más adelante sólo se contará las operaciones fundamentales, sino empezar contando todo.

Entonces, ¿cuántas veces se la j: = 1 línea de correr? ¿Cuántas veces la suma: 0 = plazo? ¿Cuántas veces se ejecutará la condición del bucle while? Las sentencias dentro del bucle while?

reunirlas en todo. Usted se dará cuenta de que el valor que se obtiene será algo así como 1 + 1 + n + n + n = 2 + 3n. por lo tanto se puede concluir que se trata de una función lineal en n.