ED2

Question 1

Algoritmos diferentes, mas capazes de resolver o mesmo problema, não necessariamente o fazem com a mesma eficiência. Essas diferenças de eficiência podem ser:

Answer 1

> Irrelevantes: para um pequeno número de elementos processados;
Crescer proporcionalmente: com o número de elementos processados.

Question 2

Para comparar a eficiência dos algoritmos foi criada uma medida chamada de:

Answer 2

Complexidade Computacional

Question 3

Complexidade Computacional, basicamente, indica o custo ao se aplicar um algoritmo, sendo:

CUSTO =

Answer 3

MEMÓRIA + TEMPO

Question 4

Para determinar se um algoritmo é o mais eficiente, podemos utilizar duas abordagens:

Answer 4

> ANÁLISE EMPÍRICA: comparação entre os programas

> ANÁLISE MATEMÁTICA: estudo das propriedades do algoritmo

Question 5

Análise Empírica

Answer 5

Avalia o custo (ou complexidade) de um algoritmo a partir da avaliação da execução do mesmo quando implementado, ou seja, um algoritmo é analisado
pela execução de seu programa correspondente;

Question 6

Vantagens da análise empírica:

Answer 6

> Avaliar o desempenho em uma determinada configuração de computador /linguagem;
Considerar custos não aparentes, como por exemplo “custo de alocação de memória”;
Comparar computadores;
Comparar linguagens.

Question 7

Dificuldades da análise empírica

Answer 7

> Há a necessidade de implementação do algoritmo, e isso depende da habilidade do programador;
O resultado pode ser mascarado pelo hardware (o computador utilizado) ou software (eventos ocorridos no momento da avaliação);

Question 8

Qual a natureza dos dados na análise empírica?

Answer 8

> Dados reais;
Aleatórios: avaliam o desempenho médio;
Perversos: avaliam o comportamento no pior caso

Question 9

Análise Matemática

Answer 9

> Permite um estudo formal de um algoritmo ao nível da ideia por trás do algoritmo;
Faz uso de um computador idealizado e simplificações que buscam considerar somente os custos dominantes do algoritmo
A medição do tempo gasto é feita de maneira independente do hardware ou da linguagem usada na sua implementação

Question 10

Vantagens da análise matemática

Answer 10

> Detalhes de baixo nível, como a linguagem de programação utilizada, o hardware no qual o algoritmo é executado, ou o conjunto de instruções da CPU, são ignorados;

> Permite entender com um algoritmo se comporta à medida que o conjunto de dados de entrada cresce. Assim, podemos expressar a relação entre o conjunto de dados de entrada e a quantidade de tempo necessária para processar esses dados gerando sua saída.

Question 11

Notação Grande-O ou “O”

Answer 11

Representa o custo (seja no tempo ou no espaço), do algoritmo no pior caso possível para todas as entradas de tamnho “n”;
 Ou seja, ela analisa o limite superior de entrada. Desse modo, podemos dizer que o comportamento do nosso algoritmo não pode nunca ultrapassar um determinado limite.

Question 12

O que descreve a notação Grande-Omega?

Answer 12

Descreve o limite assintótico inferior de um algoritmo.

Question 13

É a notação utilizada para analisar o melhor caso do algoritmo:

Answer 13

Notação Grande-Omega

Question 14

O que descreve a notação Grande-O?

Answer 14

Descreve o limite assintótico superior de um algoritmo.

Question 15

É a notação utilizada para analisar o pior caso do algoritmo:

Answer 15

Notação Grande-O

Question 16

Notação Grande-Theta

Answer 16

Descreve o limite assintótico firme ou estreito de um algoritmo.

Question 17

É a notação utilizada para analisar o limite inferior e superior do algoritmo:

Answer 17

Notação Grande-Theta

Question 18

As notações Grande-O e Grande-Omega possuem relação de:

Answer 18

Menor ou igual e maior ou igual

Question 19

As notações Pequeno-o e Pequeno-ômega possuem uma relação de:

Answer 19

Menor e maior, ou seja, não representam limites próximos da função, mas apenas estritamente.