Somando um Array e Big O Notation

Question

Como encontrar um algoritmo para calcular o valor da soma na matriz ??

Será que é algo assim?

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 como eu posso relacioná-la com o tempo de execução do algoritmo, usando a notação O

Este é o exame no ano passado e eu preciso fazer revisão para o meu exame.

Pergunta
Um arranjo A [] segurando valor inteiro n é dada
1.Give um algoritmo para calcular a soma de todo o valor na matriz
2.Find o O-notação mais simples e melhor para o tempo de execução do algoritmo.

Answer 1

A questão é encontrar o soma de todos os valores para iterate através de cada elemento na matriz e adicionar cada elemento para um valor soma temporário.

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

Uma vez que você precisa para passar por todos os elementos da matriz, este programa depende linearmente para o número de elementos . Se você tem 10 elementos, iterar 10 elementos, se você tem um milhão de você não tem outra escolha a não ser passar por todos os milhões de elementos e adicionar cada um deles. Assim, o complexidade de tempo é T (n) .

Se você está encontrando a soma de todos os elementos e você não sabe qualquer coisa sobre os dados, então você precisa olhar para todos os elementos, pelo menos uma vez. Assim, o símbolo n representa o limites mínimos. Você também não precisa de olhar para o elemento mais de uma vez. n é também o limite superior. Por isso, a complexidade é T (n).

No entanto, se você sabe alguma coisa sobre o elements..say você começa uma sequencia de n números naturais, você pode fazê-lo em tempo constante com n (n + 1) / 2. Se os dados que você recebe são aleatórias, então você não tem escolha senão fazer o acima algoritmo de tempo linear.

Answer 2

Desde n é o tamanho do array e tudo que você tem a fazer é iterate de begeinning para acabar com a notação Big O é O [n]

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

Answer 3

Eu acho que você quis dizer "enquanto j <= N", você precisa especificar isso.

O tempo de execução deve ser O (n), eu acho, como você tem apenas um loop.

Answer 4

Para calcular S para este algoritmo que você precisa para contar o número de vezes que cada linha de executa o código. Mais tarde, você só vai contar as operações fundamentais, mas começar por contar tudo.

Então, quantas vezes será o j: = 1 linha de execução? Quantas vezes a soma: = 0 prazo? Quantas vezes a condição do loop while executar? As demonstrações dentro do loop while?

Sum estes todos para cima. Você vai notar que o valor que você terá será algo como 1 + 1 + n + n + n = 2 + 3 n. assim, você pode concluir que é uma função linear no n.