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]

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 n.

Passo 2

Identificamos os laços de repetição. O primeiro comando fora dos laços faz uma divisão para calcular x[n]. Depois há um laço sobre k que vai de n-1 até 1, e dentro dele um laço sobre j que vai de k+1 até n. As iterações do laço interno somam
\sum_{k=1}^{n-1}(n-k)=\frac{n(n-1)}{2}
iterações.

Passo 3

Em cada iteração do laço interno executa-se uma multiplicação e uma adição para atualizar s. Logo, o custo do laço interno é
2 \times \frac{n(n-1)}{2}=n(n-1)
operações elementares.

Passo 4

Para cada valor de k (são n-1 passos) calcula-se depois
x[k]=\frac{b[k]-s}{a[k][k]}
que envolve uma subtração e uma divisão, ou seja, 2 operações. Além disso, há 1 divisão inicial para x[n]. Então o custo extra fora do laço interno é aproximadamente
2(n-1) + 1 = 2n - 1 = O(n).

Passo 5

Somando os custos:
  • custo do laço interno: n(n-1),
  • custo das subtrações e divisões adicionais: O(n).
Logo a função de complexidade exata em número de operações elementares é
f(n)=n(n-1) + O(n)=n^2 - n + O(n)=n^2 + O(n).

Passo 6

Como o termo dominante é n^2, na notação assintótica temos
f(n)\in \Theta(n^2).

Resposta

\Theta(n^2)

Exercícios relacionados