Exercícios de Análise de Algoritmos

breadcrumb-separator

ESTÁCIO

em 28/04/2019

Questões resolvidas

2.2-2 Considere a ordenação de n números armazenados em um vetor A encontrando primeiro o menor elemento de A e trocando-o com o elemento A[1]. Então encontre o segundo menor elemento de A e troque-o com A[2]. Continue desta maneira para os primeiros n − 1 elementos de A. Escreva um pseudocódigo para este algoritmo, que é conhecido como ordenação por seleção. Qual invariante o algoritmo mantém? Por que o algoritmo precisa executar somente para os primeiros n − 1 elementos, ao invés de para todos os n elementos? Forneça o tempo de execução do melhor caso e do pior caso do algoritmo usando a notação Θ.

2.3-3 Use indução matemática para mostrar que quando n é uma potência de 2, a solução da recorrência T (n) = { 2, se n = 2 , 2T (n/2) + n, se n = 2k, para k > 1 é T (n) = n lg n.

2.3-4 Podemos escrever um procedimento recursivo para a ordenação por inserção, como segue. Para ordenar o vetor A[1 . . n], ordenamos recursivamente A[1 . . n − 1] e então inserimos A[n] no vetor ordenado A[1 . . n − 1]. Escreva uma recorrência pata o tempo de execução deste versão recursiva da ordenação por inserção.

Conteúdos escolhidos para você

Algoritmos de Ordenação Avançados

Algoritmos de Ordenação Avançados

Algoritmos de ordenação

Algoritmos de ordenação

UNOPAR

Algoritmos de Ordenação Avançados

Algoritmos de Ordenação Avançados

ESTÁCIO

Aula 3 - Algoritmos de Ordenação Avançados

Aula 3 - Algoritmos de Ordenação Avançados

PUC-MINAS

3 - Algoritmos de Ordenação Avançados

3 - Algoritmos de Ordenação Avançados

Perguntas dessa disciplina

Os métodos de ordenação são essenciais para a organização de dados em estruturas computacionais. Existem algoritmos elementares, como Insertion Sort,

FRBA

A ordenação de dados é uma operação essencial em diversas aplicações computacionais. Para esse fim, diferentes algoritmos podem ser utilizados, cada u

Durante a execução de funções recursivas, como no cálculo de fatorial, cada chamada cria um novo contexto na pilha de execução. Essa pilha organiza...

A atividade APA será um aprendizado de uma técnica para solucionar matrizes de ordem maior do que 3x3, a qual é conhecida na literatura como Regra ...

Pergunta 3 O fatorial é uma estratégia matemática que envolve multiplicação de números consecutivos muito utilizada em computação. Em listas linea...

UNIVESP

Material

Questões resolvidas

2.2-2 Considere a ordenação de n números armazenados em um vetor A encontrando primeiro o menor elemento de A e trocando-o com o elemento A[1]. Então encontre o segundo menor elemento de A e troque-o com A[2]. Continue desta maneira para os primeiros n − 1 elementos de A. Escreva um pseudocódigo para este algoritmo, que é conhecido como ordenação por seleção. Qual invariante o algoritmo mantém? Por que o algoritmo precisa executar somente para os primeiros n − 1 elementos, ao invés de para todos os n elementos? Forneça o tempo de execução do melhor caso e do pior caso do algoritmo usando a notação Θ.

2.3-3 Use indução matemática para mostrar que quando n é uma potência de 2, a solução da recorrência T (n) = { 2, se n = 2 , 2T (n/2) + n, se n = 2k, para k > 1 é T (n) = n lg n.

2.3-4 Podemos escrever um procedimento recursivo para a ordenação por inserção, como segue. Para ordenar o vetor A[1 . . n], ordenamos recursivamente A[1 . . n − 1] e então inserimos A[n] no vetor ordenado A[1 . . n − 1]. Escreva uma recorrência pata o tempo de execução deste versão recursiva da ordenação por inserção.

Conteúdos escolhidos para você

Algoritmos de Ordenação Avançados

Algoritmos de Ordenação Avançados

Algoritmos de ordenação

Algoritmos de ordenação

UNOPAR

Algoritmos de Ordenação Avançados

Algoritmos de Ordenação Avançados

ESTÁCIO

Aula 3 - Algoritmos de Ordenação Avançados

Aula 3 - Algoritmos de Ordenação Avançados

PUC-MINAS

3 - Algoritmos de Ordenação Avançados

3 - Algoritmos de Ordenação Avançados

Perguntas dessa disciplina

Os métodos de ordenação são essenciais para a organização de dados em estruturas computacionais. Existem algoritmos elementares, como Insertion Sort,

FRBA

A ordenação de dados é uma operação essencial em diversas aplicações computacionais. Para esse fim, diferentes algoritmos podem ser utilizados, cada u

Durante a execução de funções recursivas, como no cálculo de fatorial, cada chamada cria um novo contexto na pilha de execução. Essa pilha organiza...

A atividade APA será um aprendizado de uma técnica para solucionar matrizes de ordem maior do que 3x3, a qual é conhecida na literatura como Regra ...

Pergunta 3 O fatorial é uma estratégia matemática que envolve multiplicação de números consecutivos muito utilizada em computação. Em listas linea...

UNIVESP