Questão 1 Calcule a função de complexidade computacional para o algoritmo de substituição retroativa, dado abaixo:
x[n]=b[n]/a[n][n]
para k=n-1,...,2,1
s=0
para j=k+1,...,n
s=s+a[k][j]*x[j]
x[k]=(b[k]-s)/a[k][k]
x[n]=b[n]/a[n][n]
para k=n-1,...,2,1
s=0
para j=k+1,...,n
s=s+a[k][j]*x[j]
x[k]=(b[k]-s)/a[k][k]
Passo 1
O enunciado pede a função de complexidade do algoritmo de substituição retroativa para um sistema triangular superior. O conteúdo aqui é análise de algoritmos: contamos o número de operações elementares (multiplicações, adições, subtrações e divisões) em função de
.
Passo 2
Identificamos os laços de repetição. O primeiro comando fora dos laços faz uma divisão para calcular
. Depois há um laço sobre
que vai de
até
, e dentro dele um laço sobre
que vai de
até
. As iterações do laço interno somam
iterações.
Passo 3
Em cada iteração do laço interno executa-se uma multiplicação e uma adição para atualizar
. Logo, o custo do laço interno é
operações elementares.
Passo 4
Para cada valor de
(são
passos) calcula-se depois
que envolve uma subtração e uma divisão, ou seja, 2 operações. Além disso, há 1 divisão inicial para
. Então o custo extra fora do laço interno é aproximadamente
Passo 5
Somando os custos:
- custo do laço interno:
, - custo das subtrações e divisões adicionais:
.
Logo a função de complexidade exata em número de operações elementares é
Passo 6
Como o termo dominante é
, na notação assintótica temos