Question

1) Um algoritmo A2 que necessite de f2Não = 50 unidades de memória (independente do valor de n) é um algoritmo com complexidade de espaço ____________ em função do tamanho da entrada.

Assinale a alternativa que preenche corretamente a lacuna.

Escolha uma:
a.
Polinomial

b.
Constante

c.
Linear Incorreto

d.
Recursiva

e.
Temporal

2) Considere o algoritmo de ordenação por inserção:

(imagem 1)

Independente de a entrada ser de melhor caso, caso médio ou pior caso, o espaço utilizado para memória auxiliar é:

- 1 inteiro, para armazenar a variável i;

- 1 inteiro, para armazenar a variável j;

- 1 inteiro, para armazenar a variável k;

- e 1 inteiro, para armazenar a variável t.

Sendo assim, qual a função que descreve a quantidade de memória auxiliar do algoritmo de ordenação por inserção?

Assinale a alternativa correta.

Escolha uma:
a.
fNão = 4.

b.
fNão = n + 4.

c.
fNão = 4n. Incorreto

d.
fNão = n4.

e.
fNão = log(4).

3) Sobre o cálculo da complexidade de espaço, analise as afirmativas:

I. Na memória auxiliar não são considerados os espaços necessários para: o próprio programa; a entrada; e a saída.

II. O armazenamento do próprio programa é desconsiderado pois é independente do tamanho da entrada.

III. Os armazenamentos da entrada e da saída não são considerados pois, na comparação de diferentes algoritmos que resolvem o mesmo problema, todos ocupam a mesma quantidade de memória para armazenamento da entrada e da saída.

Neste contexto, é correto o que se afirma em:

Escolha uma:
a.
II e III, apenas. Incorreto

b.
II, apenas.

c.
III, apenas.

d.
I, II e III.

e.
I e II, apenas.

Answer 1

Resposta:

1 - Constante
2 - f(n) = 4
3 - I, II e III

Explicação:

Corrigido pelo AVA