Sejam
,
e
. Apresente algoritmos, analisando sua complexidade computacional, para as seguintes operações:
a)
b)
c)
a)
b)
c)
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).
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
- Teoria: o produto escalar de y,x∈ℝᵐ é
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
- Teoria: A é n×m e x é m×1, então b∈ℝⁿ, com
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
- Teoria: A é n×m, X é m×p, então B é n×p com
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).
b) b = A x em O(n·m).
c) B = A X em O(n·m·p).