Trabalho AED

SEGUNDA LISTA DE EXERCÍCIOS
Disciplina: AED I

1. Considerando que a matriz passada como parâmetro para a função é NxN elementos inteiros, responda: public int func(int mat[][]) { int i, j, x; x = 0; (1) for(i = 0 (1); i < mat.length (N+1); i++ (N)) { for(j = 0 (N); j < mat.length (N² + N) ; j++ (N²)) { if(j > i) { x += mat[i][j]; (N² - N/2) } } } return x; (1)
}
a) Qual o objetivo dessa função e a que classe de comportamento pertence?
Somar os elementos situados acima da diagonal principal.
Comportamento : O(n²)
b) Faça a análise de complexidade e determine a função de complexidade de tempo de execução da função, levando em consideração todas as atribuições, operações, leituras, escritas e comparações.
3n² + n² / 2 + 4n - n/2 +4 =>
6n² + n² + 8n - n +8 =>
7n²/2 + 7n/2 + 8/2 => 7n² /2 + 7n /2 + 4
c) Existe melhor e pior caso para este algoritmo? Justifique sua resposta.
Não existe melhor e nem pior caso, porque o if irá executar sempre (n²/2 - n/2) independente do tamanho do vetor.
d) Apresente uma versão melhorada deste algoritmo, mostrando quais linhas poderiam ser eliminadas e/ou substituídas de forma que a complexidade de tempo diminua sem afetar o funcionamento. Dê a função de complexidade da nova versão. public int func(int mat[][]){ int i, j, x; x = 0 for(i = 0;i
7n²/2 + 7n/2 + 8/2 => 7n² /2 + 7n /2 + 4
c) Existe melhor e pior caso para este algoritmo? Justifique sua resposta.
Não existe melhor e nem pior caso, porque o if irá executar sempre (n²/2 - n/2) independente do tamanho do vetor.
d) Apresente uma versão melhorada deste algoritmo, mostrando quais linhas poderiam ser eliminadas e/ou substituídas de forma que a complexidade de tempo diminua sem afetar o funcionamento. Dê a função de complexidade da nova versão. public int func(int mat[][]){ int i, j, x; x = 0 for(i = 0;i
7n²/2 + 7n/2 + 8/2 => 7n² /2 + 7n /2 + 4
c) Existe melhor e pior caso para este algoritmo?