Algoritmos de pesquisa e ordenação

Question	Answer
O que é e como funciona Busca Sequencial?	É a forma + simples de busca, percorrendo registro por registo. O uso de uma sentinela pode tornar o algoritmo mais eficiente.
Qual a complexidade da Busca Sequencial?	No pior caso: O(n)
O que é e como funciona Busca Binária?	Em uma arranjo ordenado, pode-se comparar o elemento procurado com o elemento central. Se este for menor, procura-sena metade inferior do arranjo. Se maior, busca-se na parte superior. Em cada passo o tamanho do arranjo é dividido por 2.
Quais as vantagens e desvantagens desse método?	É vantajoso por ser eficiente na busca e simples de implementar. Porem nem todo arranjo é ordenado e a inserção e remoção pedem realocação de elementos.
Qual a complexidade da Busca Binária?	Pior caso: O(logN). Mesma altura de uma arvore balanceada.
O que é e como funcionam as Arvores de Busca?	São estruturas que organizam os dados de forma hierárquica.
Quais as complexidades de uma arvore?	No melhor caso: O(logN) para arvores balanceadas. Pior caso: O(N) para arvores desbalanceadas.
O que é e como funcionam as Tabelas Hashing?	São estruturas que procuram realizar as operações em tempos constantes.
Quais as vantagens e desvantagens das tabelas Hash?	Para uma boa estrutura Hash, os acessos são praticamente diretos. Porem quando esta não é bem utilizada, o uso ineficiente do espaço de armazenamento pode gerar vários conflitos, aumentando o tempo das operações.
Qual a complexidade da Hash?	Pior caso: O(N)
Cite dois algoritmos de ordenação baseados em troca.	1.Bubble-Sort 2. Quick-Sort
Explique o funcionamento do Bubble-Sort.	Também conhecido como método Bolha, este percorre o conjunto varias vezes e a cada iteração, compara cada elemento com o seu sucessor e troca estes de lugar caso a ordem esteja incorreta.
Qual a complexidade do método Bolha?	Melhor caso: O(n) para algoritmos "melhorados" Pior caso: O(n²)
Explique o funcionamento do Quick-Sort.	Neste a troca de elementos mais distantes são mais efetivas. É escolhido um elemento pivô e percorre-se o vetor nas duas direções. Quando i e j se cruzarem, a iteração é finalizada e o pivô troca de lugar com i. Então os dois sub vetores acima e baixo do pivô são ordenados.
Qual a complexidade do Quick-Sort?	Melhor Caso: O(nlogN) Pior Caso: O(n²) quando o vetor está ordenado
Cite dois exemplos de algoritmos de ordenação por Inserção.	1. Inserção Simples 2. Shell-Sort
Explique o que é e como funciona a ordenação por Inserção Simples.	Os elementos são realocados, ordenando o conjunto inserindo os elementos em um subconjunto já ordenado.
Quando este algoritmo é vantajoso?	É melhor que o Bolha por fazer menos comparações, uma vez que a parte ordenada não é testada novamente. Eficiente para arquivos já ordenados.
Qual a complexidade da ordenação por Inserção Simples?	Melhor Caso: O(n) Pior Caso: O(n²) para vetores ordenados inversamente
Explique como funciona o algoritmo Shell-Sort.	Dividir a entrada em k subgrupos e aplicar a inserção simples acada um, sendo que K é reduzido sucessivamente
Qual a complexidade do Shell-Sort?	Melhor Caso: O(n) Pior Caso: O(n(logn)²) porem é difícil determinar uma complexidade exata pois depende de K
Cite dois exemplos de ordenação por seleção.	1. Seleção direta 2. Heap-sort
Explique a ordenação por Seleção Direta.	Coloca-se o menor valor sempre na primeira posição, e assim por diante para os n-1 elementos restantes.
Quando esse algoritmo é vantajoso?	Não existe melhora para vetores ordenados ou não. Porem, este ainda é melhor que o método bolha. Útil para numero pequeno de elementos.
Qual a complexidade deste algoritmo?	Tanto para melhor e o pior caso a complexidade é de O(n²)
Como funciona o algoritmo de ordenação Heap-sort?	É um vetor que representa uma arvore binária QUASE COMPLETA. A árvore tem seus nos folhas, no máximo, em dois níveis, sendo que as folhas devem ser o mais à esquerda possível. A raiz sempre na posição zero do vetor.
Qual a posição dos filhos de um nó K em Heap-Sort?	filho esquerdo: 2k+1 filho direito: 2k+2
Qual a posição do pai de um nó K em Heap-Sort?	(k-1)/2
Qual a posição das folhas de um Heap-Sort?	De n/2 em diante
Quais os tipos de heap que existem?	Heap maximo: pai>filhos Heap minimo: pai<filhos
Qual a complexidade do heap-sort?	Melhor caso: O(nlogN) Pior caso: O(nlogN)
Cite um algoritmo de ordenação por intercalação.	1. Merge-Sort
Explique esse algoritmo	Um vetor é dividido ao meio recursivamente. Cada metade é ordenada e unidas gradativamente, deixando o arranjo ordenado
Qual a complexidade do Merge-Sort	Θ(n) ou Θ(nlogN) dependendo da versão utilizada.
Para conjuntos aleatórios, quais os melhores algoritmos?	Shell-Sort, Quick-Sort e Heap-Sort são rápidos e constantes para um conjunto grande de dados. Dentre estes, o Quick-Sort é o mais rápido.
Para conjuntos ordenados, quais tem melhores desempenho?	Inserção Simples tem melhor comportamento
Quais algoritmos tem melhor comportamento para conjuntos ordenados inversamente?	Shell-Sort, Quick-Sort e Merge-Sort se comportam bem, porem quick é melhor. Inserção tem o pior desempenho nesse cenário
Shell-Sort e Quick-Sort são sensíveis para quais cenários?	Para arranjos ordenados (crescente e decrescente)
HeapSort é sensível para quais cenários?	É pouco sensível para arranjos ordenados (crescente e decrescente)

Next up

Algoritmos de pesquisa e ordenação

Description

Resource summary

Similar

	Created by hethini ribeiro over 7 years ago

	Copied by Douglas Costa about 7 years ago