Question

A complexidade pode ser calculada através do tempo de execução do algoritmo determinado pelas instruções executadas :quanto “tempo” é necessário para computar o resultado para uma instância do problema de tamanho n; e também do espaço de memória utilizado pelo algoritmo : quanto “espaço de memória/disco” é preciso para armazenar a(s) estrutura(s) utilizada(s) pelo algoritmo. Uma das principais medidas de complexidade é a quantidade de vezes que a operação fundamental é executada. Por exemplo, para um algoritmo de ordenação, uma operação fundamental é a comparação entre elementos quando à ordem.

Considere o seguinte algoritmo de multiplicação de matrizes:



programa multiplica_matrizes;
matriz mat1, mat2, mat3;
inteiro linha, coluna, i, acumula;
"leia mat1";
"leia mat2";
"verifique se mat1 é compativel com mat2";
para linha de 1 até "numero de linhas de mat1" faça
para coluna de 1 até "numero de colunas de mat2" faça
acumula=0;
para i de 1 até "numero de colunas de mat1" faça
acumula=acumula+mat1[linha][i]*mat2[i][coluna];
fimpara;
mat3[linha][coluna]=acumula;
fimpara;
fimpara;
imprima mat3;
fim programa;

Sendo a operação mais importante a multiplicação entre dois elementos. Assinale a alternativa que apresenta a complexidade deste algoritmo.

Alternativas:

a)
O(logn)

b)
O(n)

c)
O(1)

d)
O(n²)

e)
O(n3)

Answer 1

Resposta:

O(n²)

letra d)

confirmado no AVA

Explicação:

Em função da ordem da matriz