Somando um Array e Big O Notation
Pergunta
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.
Solução
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
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.
Outras dicas
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
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.
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.