Sejam A in R^n times m, X in R^m times p, B in R^n times p, x, y in R^m, b in R^n e beta in R. Apresente algoritmos, analisando sua complexidade computacional, para as seguintes operações:
a) beta=y cdot x
b) b=A x
c) B=A X

Passo 1

Beleza, temos um exercício de Álgebra Linear que pede para a gente apresentar algoritmos (tipo pseudocódigo) e analisar a complexidade computacional de três operações básicas:
a) o produto escalar de dois vetores em ℝᵐ,
b) a multiplicação de uma matriz A∈ℝⁿˣᵐ por um vetor x∈ℝᵐ,
c) a multiplicação de duas matrizes A∈ℝⁿˣᵐ e X∈ℝᵐˣᵖ.
Para resolver, vamos precisar entender que cada operação aritmética (soma, multiplicação) conta como custo 1, e que loops aninhados geram a contagem de operações em função dos tamanhos (n, m, p).

Passo 2

Operação (a): β = y · x
  1. Teoria: o produto escalar de y,x∈ℝᵐ é beta ;=; ycdot x ;=;sumi=1^myi,xi
    2) Pseudocódigo informal:
    β ← 0 para i de 1 até m faça β ← β + y[i] * x[i] fim para
    3) Análise de complexidade:
    - Em cada iteração fazemos 1 multiplicação e 1 soma → 2 operações.
    - Total de iterações = m.
    → Complexidade: O(m).

Passo 3

Operação (b): b = A x
  1. Teoria: A é n×m e x é m×1, então b∈ℝⁿ, com bi ;=;sumj=1^mAi j,xj,, i=1,dots,n
    2) Pseudocódigo informal:
    para i de 1 até n faça soma ← 0 para j de 1 até m faça soma ← soma + A[i][j] * x[j] fim para b[i] ← soma fim para
    3) Análise de complexidade:
    - Cada par (i,j) gera 1 multiplicação + 1 soma = 2 ops.
    - Total de pares = n·m.
    → Complexidade: O(n·m).

Passo 4

Operação ©: B = A X
  1. Teoria: A é n×m, X é m×p, então B é n×p com Bi k ;=;sumj=1^mAi j,Xj k,, i=1,dots,n,;k=1,dots,p
    2) Pseudocódigo informal:
    para i de 1 até n faça para k de 1 até p faça soma ← 0 para j de 1 até m faça soma ← soma + A[i][j] * X[j][k] fim para B[i][k] ← soma fim para fim para
    3) Análise de complexidade:
    - Cada tripla (i,j,k) faz 1 multiplicação + 1 soma = 2 ops.
    - Total de triplas = n·m·p.
    → Complexidade: O(n·m·p).

Resposta

a) β = y·x em O(m).
b) b = A x em O(n·m).
c) B = A X em O(n·m·p).

Exercícios relacionados