2

Tenho um vetor A de tamanho n. Tenho que calcular a soma parcial de cada elemento e escrever na matriz B[i,j].

O pseudo-código mostra uma solução O(n^2);

  For i = 1, 2, . . . , n
    For j = i + 1, i + 2, . . . , n
      B[i, j] <- A[i] + A[i+1] + ... +  A[j];
   Endfor
  Endfor

Existe uma solução O(n) ou O(log n)? Como seria?

1 Resposta 1

2

Da forma que está escrito, o seu algoritmo é O(N3). Tem um terceiro loop implícito na parte que você soma os A[i]s.

Na forma atual do problema, não tem como ter um algoritmo melhor que O(N2). Você tem N*(N-1)/2 elementos para preencher na matriz B então só a parte de escrever a saída já vai ser O(N2).

Se você mudar a definição de B para ser um vetor unidimensional onde B[i] significa a soma de A[1] até A[n], ai dá pra fazer em O(N). O truque é reaproveitar os valores já calculados de B nas suas contas. (tente fazer isso sem perguntar antes - é um ótimo exercício)

O(log N) não dá porque no mínimo você vai ter que percorrer o vetor A uma vez para ler os seus elementos e isso já vai dar O(N).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .