Conte o número de operações realizadas para computar o produto de uma matriz n times n por um vetor n times 1.

Passo 1

Beleza! O enunciado pede pra contar quantas operações a gente faz ao multiplicar uma matriz quadrada de tamanho ntimes n por um vetor de tamanho ntimes1.
O conteúdo é simplesmente produto matriz-vetor e contagem de operações aritméticas (multiplicações e adições). A gente vai usar o fato de que cada entrada do resultado é um produto escalar de duas listas de tamanho n, e aí somar tudo.

Passo 2

Vamos ver uma única linha da matriz (tamanho 1times n) multiplicada pelo vetor (tamanho ntimes1).
Produto escalar significa:
yi = Ai1x1 + Ai2x2 + cdots + Ainxn.
Para computar isso, fazemos:
  • n multiplicações ( Aijtimes xj, pra cada j=1,dots,n).
  • n-1 adições (a gente soma esses n produtos em cadeia: primeiro soma dois, depois soma o terceiro ao resultado, e por aí vai).

Passo 3

Como a matriz tem n linhas, a gente repete esse processo n vezes, uma vez pra cada linha.
Então no total temos:
  • Multiplicações: n operações por linha times n linhas = n times n = n^2.
  • Adições: (n-1) operações por linha times n linhas = ntimes (n-1) = n(n-1).

Passo 4

Se você quiser o total de operações (contando multiplicaçõese adições juntas), é só somar:
n^2 ;+; n(n-1);=;n^2 + n^2 - n;=;2n^2 - n

Resposta

Número de multiplicações: n^2.
Número de adições: n(n-1).
Total de operações: 2n^2 - n.

Exercícios relacionados