Análise de Algoritmo

A visually appealing illustration depicting algorithms, sorting techniques, and mathematical induction concepts, aimed at a tech-savvy audience, in a modern and vibrant color palette.

Desvendando Algoritmos

Teste seus conhecimentos sobre algoritmos e análise de complexidade com este desafiador quiz. Se você é estudante, professor ou apenas entusiasta de programação, este quiz é ideal para você!

Aprenda sobre algoritmos de ordenação
Entenda princípios de indução matemática
Explore notações assintóticas

9 Questions2 MinutesCreated by AnalyzingData42

Quando um algoritmo contém uma ________ a si mesmo, o ________ pode frequentemente ser _______ por uma _______.

Chamada recursiva, tempo de execução, descrito, equação de recorrência.

recorrência, nível de complexidade, aumentado, quantidade adicional de tempo.

referência, tempo de execução, reduzido, quantidade n.

instância referenciada, nível de complexidade, aumentado, instância de tamanho n.

Em relação aos algoritmos de ordenação MergeSort e InsertionSort, podemos afirmar:

O algoritmo MergeSort utiliza a estratégia de intercalação para realizar a ordenação de uma instância de entrada de tamanho n.

No algoritmo InsertionSort podemos dizer que a estratégia é ir percorrendo o vetor de entrada (instância de entrada) e formando um vetor ordenado a cada novo elemento lido. Assim podemos dizer que para cada elemento lido no vetor de entrada, a tarefa será inseri-lo em um vetor já ordenado, de tal forma que o vetor resultante também esteja ordenado.

Uma implementação possível para o algoritmo MergeSort, é através do uso de recursão.

Em relação ao primeiro princípio e o segundo princípio da indução matemática, podemos afirmar:

Os dois princípios diferem na segunda proposição (proposição 2), onde no primeiro princípio precisamos provar que " (∀ k )[P(k) verdade → P(k + 1) verdade] " , ao passo que no segundo princípio precisamos provar que " P(k) verdade para todo r, 1≤ r ≤ k → P(k + 1) verdade".

Somente prova das proposições dos dois princípios da indução é suficiente de forma a garantirmos a proposição "“P(n) é verdade para todo inteiro positivo n. A prova de somente um dos princípios é incompleta.

A vantagem no uso do segundo princípio da indução é que não precisamos provar a base da indução (P(1)).

Em relação a recorrência, podemos afirmar:

Quando um algoritmo contém uma chamada recursiva a si próprio, seu tempo de execução pode ser descrito frequentemente por uma recorrência, que descreve o tempo de execução global para um problema de tamanho n em termos do tempo de execução para entradas menores.

Uma das utilizações da recorrência é no uso da estratégia de divisão e conquista utilizada por alguns algoritmos.

As equações de recorrência nos ajudam a resolver problemas no tempo de execução dos algoritmos.

Em relação aos algoritmos de ordenação MergeSort e Insertion podemos afirmar:

O algoritmo InsertionSort é mais eficiente que algoritmo MergeSort, uma vez que possui tempo de execução Θ (n lg( n)), ao passo que o algoritmo MergeSort tem tempo de execução de pior caso Θ (n²).

O algoritmo Insertion sort pode levar quantidades de tempos diferentes para ordenar duas sequências de entrada de mesmo tamanho n, ao passo que o algoritmo MergeSort leva o mesmo tempo para qualquer entrada de tamanho n.

A etapa de divisão no algoritmo MergeSort simplesmente calcula o ponto médio do subarranjo, o que demora um tempo constante, assim é Θ (1).

O _________ de indução matemática é __________. A conclusão é uma ________ da forma “________ para todo inteiro positivo n”.

Primeiro princípio, um condicional, proposição, P(n) é verdade.

Teorema, universal, solução, A indução vale

Segundo princípio, uma recursão, equação recursiva, P(k+1) = P(k) +P(1)

Terceiro princípio, indutivo, proposição, A indução vale

Em relação a notação assintótica para análise de algoritmos podemos afirmar:

A notação O nos dá um limite superior para o tempo de execução de um algoritmo.

A notação Ω nos dá um limitante inferior para o tempo de execução de um algoritmo.

A notação Θ é utilizada quando é possível estabelecer um limite superior e um limite inferior para o tempo de execução de um algoritmo a partir de uma mesma função.

Em relação aos modelos computacionais, podemos afirmar que são exemplos de modelos computacionais:

Máquinas de Turing, Máquinas de Estados Finitos, Máquinas de estados infinitos.

modelo restritivo, modelo regular, modelo assintótico.

Máquina de Turing, Modelo RAM, Máquinas de Estados Finitos.

Modelo restritivo, modelo regular, modelo assintótico.

O tempo de _________ nos dá uma medida da _________ de um algoritmo, e está associado ao _________ pelo algoritmo para nos fornecer uma saída para _________.

execução, complexidade, número de linhas de código utilizadas, variável de entrada.

execução, eficiência, número de passos gastos, uma instância de entrada.

espera, velocidade, recurso consumido, uma constante de entrada.

análise, complexidade, custo demandado, um problema.

Análise de Algoritmo

Desvendando Algoritmos

More Quizzes