estrutura de dados

Trabalho Final
Estrutura de Dados
Sangela Nobre de Gois
PVI - Informática

1) A notação O Grande é uma função matemática que indica o crescimento de uma função em relação a outra, de modo que em computação "O Grande" explica que um algoritmo utiliza espaço e tempo de execução estritamente menor ou igual a uma função matemática. Ex: O método bolha de ordenação tem tempo de computação O(n), isso indica que ele leva no máximo um tempo proporcional a n.
2.a) O algoritmo de pesquisa binária recebe um vetor ordenado como entrada e calcula o meio do vetor e compara se o elemento central é o valor buscado, senão cada parte do vetor se torna um novo vetor se encontrar o elemento central como valor buscado ele para, ele utiliza o método de divisa e conquista.
O algoritmo de pesquisa sequencial busca o elemento sequencialmente em um vetor ordenado a partir do primeiro elemento até encontrá-lo e da uma resposta positiva ou contrária.
2.b)
Melhor Caso:
Binária: O (1), tempo contante, o elemento buscado é o elemento central. Sequencial: O (1), o elemento buscado o primeiro elemento do vetor.
Pior Caso:
Binária: O (logn), o elemento está no vetor, nas posições não centrais.
Sequancial: O (n), o elemento buscado não está no início podendo ser no máximo o último.

2.c) public class binária (){ public static void main (string v) int a[n] = {1,2,3,4,...,n}; //n elementos int meio, valor =3; //valor buscado int esq, dir = a.length_1;

'

while(esqvalor) dir=meio-1; out else System.println("vetor encontrado");
}
}

3.a)
Bubble sort é um algoritmo simples de ordenação que funciona ordenando os elementos de dois a dois de modo que ele precisa para ordenar um vetor n-1 interações no pior caso. Ele é utilizado para ordenar pequenos vetores, funciona dentro de outros métodos de organização quando a lista se torna pequena.
O Shell sort é um método de ordenação por divisão e conquista, que divide um vetor em vetores menores e ordena-os. A