Mostrando postagens com marcador Algorithm. Mostrar todas as postagens
Mostrando postagens com marcador Algorithm. Mostrar todas as postagens
domingo, 27 de outubro de 2013
Data Structures
- Hash Table
Combinam uma tabela a uma função. Particiona o conjunto de dados a fim de facilitar a busca.
Aloca nos buckets
Vetor de vetores dinâmicos. Função matemática elaborada, ex: F(x) = x%10
Dispersão quando um buckets fica mais cheio. 16 bytes MD5, SHA-1
- Grafo
Grafo G consiste de um conjunto finito de elementos chamado vértice e um conjunto de pares não ordenados de vértices chamado arestas.
- algoritmo de bellman-ford
- Arvore
Binária
Raiz tem até dois filhos.
B
Raiz tem de 2 até N+1 filhos.
Nós interno tem [N/2]
Filhs [N/2]-1, N-1
Folhas sempre no mesmo nível
Ao remover
Redistribuição
Se os irmãos tiverem mais que o mínimo
Concatenação
Se os irmãos tiverem o mínimo
Ao remover o não folha, vai jogando pra baixo até virar folha.
Arvore Balanceada AVL
Se para cada nós as sub-arvores a direita ou esquerda tiverem a mesma altura ou de 1.
Fator de balanceamento(-1, 0 ou 1)
Se fator + rotação à esquerda
Se fator - rotação à direita
Arvore T
Baseada na AVL sendo binária e auto-balanceada.
Da B por ter estrutura de índice.
Balenaceamento como na AVL, mas com menos frequencia pq dados se movimento no nó.
Red-Black Tree
Tipo especial de arvore binária.
O nó raíz é negro.
Um nó vermelho só pode ter filhos negros. Nós inserido é sempre vermelho.
Todos os caminho a partir da raíz tem o mesmo número de nós pretos.
Splay tree
Itens mais acessados são movidos pra cima.
- Coloração de gráfico (coloring algorithm)
Para cada vértice, percorrer os seus vizinhos e colorí-los.
Escolher o nó com maior número de ligações.
- Minimax
Minimax for next move
Assume o oponente força vc a ir no pior caminho.
Maximizo a minha jogada e minimizo a adversário
- Alfta-Beta
Começa como o MinMax. Não expande a nós irrelevantes, pois faz a poda.
Na recursão pergunta se tem algum antecessor com valor "ctrário" maior ou menor.
Ex, se eu tive no MIN, pergunta se tem algum ancestral MAX maior que o elemento?
Se tiver no MAX, existe algum ancestral MIN menor que o elemento?
List of some Sort Methods
- Método de ordenação
BUBBLE
Um loop eterno. Vai trocando até acaber.
Funciona como uma bolha
Ordem N2
INSERTION
for dentro de for. No segundo for, parte do elemento definido no for anterior e vai voltando até o início tentando trocar.
N2.
//Algorithm
1: for(j = 1; j < length; j++) // Note!
2: {
3: keyelement = array[j];
4: for (i = j - 1; (i >= 0) && (array[i] < keyelement); i--)
5: {
6: array[i+1] = array[i];
7: }
8: array[i+1] = keyelement;
9: }
for dentro de for, em cada passada, escolhe o menor e troca no final do loop
//Algorithm
1: for (i= length - 1; i > 0; i--)
2: {
3: firstelement = 0;
4: for (j=1; j<=i; j++)
5: {
6: if (array[j] < array[firstelement])
7: firstelement = j;
8: }
9: temp = array[firstelement];
10: array[firstelement] = array[i];
11: array[i] = temp;
12: }
Generaliza o insert sort. Permite que itemns longe sejam trocado.
Começa com ordenamentos entre elementos em distancia = N/2 .
Enquanto tiver troca continua.
Depois faz o mesmo para o distancia = distancia/2.
Repete até distancia < 1; //Algorithm
1: d = length;
2: flag = 1;
3: while ( flag || (d > 1))
4: {
5: flag = 0;
6: d = (d + 1)/2;
7: for (i =0; i < (length - d); i++)
8: {
9: if (array[i + d] > array[i])
10: {
11: tmp = array[i+d];
12: array[i + d] = array[i];
13: array[i] = tmp;
14: flag = 1;
15: }
16: }
17: }
Algorithm of Divide and conquer. Lista dividida em 2, depois essa é dividida em dois.
Faz o mesmo para a direita e pra esquerda. Depois faz o merge.
No merge criar um helper com os valores do vetor e tem-se low, middle e high. Percorre-se enquanto i<=middle e j<=high. Se o valor o i < valor do helper[j], copia v[i] e i++, senão v[j] e j++. Copia o resto do do helper para o v
1: private void mergesort(int low, int high) {
2: // Check if low is smaller then high, if not then the array is sorted
3: if (low < high) {
4: // Get the index of the element which is in the middle
5: int middle = low + (high - low) / 2;
6: // Sort the left side of the array
7: mergesort(low, middle);
8: // Sort the right side of the array
9: mergesort(middle + 1, high);
10: // Combine them both
11: merge(low, middle, high);
12: }
13: }
14: private void merge(int low, int middle, int high) {
15: // Copy both parts into the helper array
16: for (int i = low; i <= high; i++) {
17: helper[i] = numbers[i];
18: }
19: int i = low;
20: int j = middle + 1;
21: int k = low;
22: // Copy the smallest values from either the left or the right side back
23: // to the original array
24: while (i <= middle && j <= high) {
25: if (helper[i] <= helper[j]) {
26: numbers[k] = helper[i];
27: i++;
28: } else {
29: numbers[k] = helper[j];
30: j++;
31: }
32: k++;
33: }
34: // Copy the rest of the left side of the array into the target array
35: while (i <= middle) {
36: numbers[k] = helper[i];
37: k++;
38: i++;
39: }
40: }
QUICK SORT
http://www.youtube.com/watch?v=gu7x-jgzuOU
Método de dividir e conquistar. Escolhe o pivo e ordena de acordo com ele.
escolhe um pivot, no N/2.
Depois divide em duas listas. E joga os maiores a direita do pivo e os menores a esquerda através das trocas sucessivas.
i=low, j=high. Faz o mesmo à direita e a esquerda.
1: private void quicksort(int low, int high) {
2: int i = low, j = high;
3: // Get the pivot element from the middle of the list
4: int pivot = numbers[low + (high-low)/2];
5: // Divide into two lists
6: while (i <= j) {
7: // If the current value from the left list is smaller then the pivot
8: // element then get the next element from the left list
9: while (numbers[i] < pivot) {
10: i++;
11: }
12: // If the current value from the right list is larger then the pivot
13: // element then get the next element from the right list
14: while (numbers[j] > pivot) {
15: j--;
16: }
17: // If we have found a values in the left list which is larger then
18: // the pivot element and if we have found a value in the right list
19: // which is smaller then the pivot element then we exchange the
20: // values.
21: // As we are done we can increase i and j
22: if (i <= j) {
23: exchange(i, j);
24: i++;
25: j--;
26: }
27: }
28: // Recursion
29: if (low < j)
30: quicksort(low, j);
31: if (i < high)
32: quicksort(i, high);
33: }
HEAP (nLogn) com pior = caso médio
Cria-se uma arvore heap na ordem da lista que vira uma árvore balanceada.
Ordena: Troca os valores das sub-arvores com os elementos acima, caso o valor seja maior recursivamente até chegar à raiz.
Envia esse valor pro vetor. Como a raiz ficará vazia, pegue qualquer elemento folha e jogue pra raíz.
A ideia é dos menores valores irem sendo jogados para a raiz.
http://sciencetechpedia.blogspot.com.au/2012/11/heap-sort-using-java.html
Assinar:
Postagens (Atom)