As Medidas Tempo e Espaço São Respectivamente Relacionadas

Questionário

1. As medidas Tempo e Espaço são respectivamente relacionadas à:

1. quantidade de memória e velocidade;
2. memória RAM e Processador;
3. Números de execuções e Quantidade de memória;
4. nda;

1. Qual operação fundamental para um algoritmo de ordenação?

A comparação de valores dos registros quanto a ordem.

1. Quais são os três cenários analisados na Complexidade de Algoritmos?

Melhor caso; Pior caso; Caso médio

1. Qual é a análise definida pelo crescimento da complexidade para entradas suficientemente grandes?

A complexidade assintótica.

1. Se o algoritmo processa entradas do tamanho 'n' no tempo c * , para alguma constante 'c', então dizemos que a complexidade de tempo do algoritmo é O(n²), onde se lê ordem n².[pic 1]

1. Quais as funções definem:

1. limite assintótico superior: f(n)
2. limite assintótico inferior: g(n)

Expressão	Nome
O(1)	Constante
O(log n)	Logaritmica
O()[pic 2]	Log quadrado
	Linear
O(nlog n)	N Log n
	Quadrática
O()[pic 3]	Cúbica
	Exponencial

1. Complete as expressões:

1. Calcule a notação O da seguinte função: 10 + 18n + 30.[pic 4]

Resposta: O(n2)

1. Qual é a função que se n dobra, o número de operação quadruplica

Resposta: O(n2)

1. Expresse de forma matemática a eficiência do algoritmo quando o mesmo possui 2 laços de repetição.

Resposta: O(n2)

1. Qual é a eficiência do algoritmo abaixo: O(n³)

coluna ← 1

  enquanto (coluna ≤ tamanho_da_matriz ) faça

      col ← 1

      enquanto (col ≤ tamanho_da_matriz ) faça

          m3 [ linha, col ] ← 0

          k ← 1

          enquanto (k ≤ tamanho_da_matriz ) faça

              m3 [ linha, col ] ← m3 [ linha, col ] + m1 [ linha, k ] * m2 [ k, col ]

              k ← k + 1

          fim-enquanto

          col ← col + 1

       fim-enquanto

       coluna ← coluna + 1

       linha ← linha + 1

   fim-enquanto

1. Qual é a operação preponderante em um algoritmo de Busca Linear?

Comparação de valores dos registros.

1. Em um algoritmo de Ordenação por Seleção, onde é gasto o maior tempo de execução?

     Na realização do laço interno.

1. Qual é a complexidade de um algoritmo de Ordenação por Seleção?

O algoritmo é da ordem O(n²).

1. Qual método de seleção é um método estável, pois deixa os registros com chaves iguais na mesma posição relativa:

Ordenação por Inserção.

1. Defina a teoria dos Grafos.

É o ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.

1. Dê um exemplo de um problema que podemos resolver com a teoria dos Grafos.

Descobrir qual é o roteiro mais curto para visitar as principais cidades de uma região turística.

...