Wondershare EdrawMind
Galeria de mapas mentais Conceitos básicos de estruturas de dados e algoritmos
- 11
Conceitos básicos de estruturas de dados e algoritmos
Introduziu os dois aspectos principais da estrutura de dados e algoritmo. As estruturas de dados incluem principalmente estruturas lineares e estruturas não lineares. As estruturas lineares incluem listas lineares, pilhas, filas, strings, matrizes, matrizes, listas generalizadas, etc. Estruturas não lineares incluem árvores, árvores binárias, florestas, gráficos, etc. As operações das estruturas de dados incluem principalmente pesquisa e classificação. Em termos de algoritmos, introduz principalmente algoritmos convencionais, como método de divisão e conquista, método de programação dinâmica, etc., bem como algoritmos de mineração de dados, algoritmos de otimização inteligente, etc.
Editado em 2022-06-30 12:23:27
- Microbiologia medica Infezione batterica e immunità
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
- teoria cinetica dei gas
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
- Breve História do Tempo
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
Conceitos básicos de estruturas de dados e algoritmos
- Microbiologia medica Infezione batterica e immunità
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
- teoria cinetica dei gas
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
- Breve História do Tempo
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
- Recomendado para você
- Descrição
![[Notas de estudo] Árvore de estrutura de dados](https://edrawcloudpublicus.s3.amazonaws.com/work/5594777/2024-6-5/1717595706/thumb.png?x-oss-process=image/resize,w_300,m_lfit)
estrutura de dados
estrutura de dados
conceito
definição
É uma coleção de elementos de dados e a relação entre os elementos e o método de construção
A relação entre os elementos é a estrutura lógica dos dados
O armazenamento de elementos de dados e relacionamentos entre elementos é chamado de estrutura de armazenamento (/estrutura física)
Três elementos
estrutura lógica
estrutura de armazenamento
Operação
Classifique de acordo com a estrutura lógica
estrutura linear
estrutura não linear
estrutura de árvore
estrutura gráfica
Sobre "Estrutura Linear"
definição
Usado para descrever relacionamentos de dados com um único predecessor e sucessor no mundo objetivo
Características
Existe uma relação linear entre os elementos de dados, ou seja, os elementos são organizados "um após o outro"
Classificação
mesa linear
definição
É uma sequência finita de n (n≥0) elementos (estruturalmente indivisíveis), geralmente expressa como (a1,a2,...,an)
Operações básicas
inserir
excluir
Encontrar
estrutura de armazenamento
armazenamento sequencial
Use um conjunto de unidades de armazenamento com endereços consecutivos para armazenar elementos de dados sequencialmente na tabela linear
O local de armazenamento do i-ésimo elemento ai
LOC(ai) = LOC(a1) (i-1) x L
armazenamento em cadeia
Armazene elementos de dados usando nós vinculados por ponteiros
estrutura do nó
campo de dados
Usado para armazenar o valor do elemento de dados
campo de ponteiro
Usado para armazenar as informações de posição do antecessor imediato ou sucessor imediato do elemento atual
Classificação
Lista vinculada linear (ou lista vinculada unilateral)
Existe apenas um campo de ponteiro no nó
Lista duplamente vinculada
Cada nó possui 2 ponteiros
lista vinculada circular
O ponteiro do nó no final da tabela aponta para o nó no topo da tabela
lista vinculada estática
Use matrizes para descrever a estrutura de armazenamento vinculada de listas lineares
pilha
definição
O armazenamento e a recuperação de dados só podem ser alcançados através de uma extremidade (LIFO, Last In First Out, LIFO)
Operações básicas
Pilha de inicialização InitStack(S)
Determinando que a pilha está vazia IsEmpty(S)
Empurre para a pilha Push(S, x)
Pop(S)
Leia o elemento superior da pilha Top(S)
estrutura de armazenamento
armazenamento sequencial
armazenamento em cadeia
aplicativo
Avaliação de expressão
correspondência de colchetes
Convertendo um processo recursivo em um processo não recursivo
fila
definição
Os elementos só podem ser inseridos em uma extremidade da tabela e excluídos na outra extremidade da tabela (First In First Out, FIFO)
Operações básicas
Inicialize a fila InitQueue(Q)
Equipe de juízes vazia IsEmpty(Q)
Enfileirar EnQueue(Q, x)
Desenfileirar DelQueue(Q)
Leia o elemento principal da fila FrontQue(Q)
estrutura de armazenamento
armazenamento sequencial
fila sequencial
fila circular
armazenamento em cadeia
fila em cadeia
corda
definição
Apenas uma sequência limitada de caracteres. Geralmente registrado como S='a1a2...an', S é o nome da string e a string após = é o valor da string
conceito básico
String vazia; string de espaço;
Operações básicas
Operação de atribuição StrAssign(s, t)
Operação de concatenação Concat(s, t)
Comprimento da string StrLength(s)
Comparação de strings StrCompare(s, t)
Encontre a substring SubString(s, start, len)
estrutura de armazenamento
armazenamento sequencial
armazenamento em cadeia
correspondência de padrões
definição
A operação de posicionamento de substrings é chamada de correspondência de padrões de string.
Substring também é chamada de string padrão
algoritmo de correspondência
Algoritmo de correspondência de padrões ingênuo
Algoritmo Brut-Foss
Algoritmo de correspondência de padrões aprimorado
Algoritmo KMP
promoção
variedade
definição
Uma matriz é uma extensão de uma lista linear de comprimento fixo em termos de dimensões, ou seja, os elementos de uma lista linear também são uma lista linear.
Uma matriz N-dimensional é uma estrutura de dados "isomórfica", com cada elemento de dados tendo o mesmo tipo e estrutura consistente.
Características
Número fixo de elementos de dados
Os elementos de dados têm o mesmo tipo
O relacionamento subscrito dos elementos de dados tem restrições de limite superior e inferior, e os subscritos são ordenados
Operações básicas
Dado um conjunto de subscritos, acesse elementos de dados
Dado um conjunto de subscritos, modifique o elemento de dados
estrutura de armazenamento
armazenamento sequencial
matriz
definição
Uma matriz é um objeto matemático. Aqui estudamos principalmente como fazer com que várias operações na matriz sejam executadas de forma eficiente e, ao mesmo tempo, economizar espaço de armazenamento.
Classificação
matriz especial
A distribuição de elementos com o mesmo valor ou 0 elementos na matriz possui certas regras.
Classificação
Matriz simétrica
matriz diagonal
matriz triangular
matriz esparsa
Elementos com o mesmo valor ou 0 elementos são distribuídos irregularmente na matriz
armazenar
Use o trio (i, j, aij) para armazenar o número da linha, o número da coluna e o valor de 1 elemento
estrutura de armazenamento
armazenamento sequencial
tabela de sequência tripla
armazenamento em cadeia
lista vinculada
tabela generalizada
definição
é uma sequência finita que consiste em 0 ou mais elementos únicos ou sublistas
comprimento
número de elementos
profundidade
O número máximo de níveis de colchetes contidos em uma tabela generalizada após expansão
Operações básicas
inserir
excluir
Encontrar
estrutura de armazenamento
armazenamento em cadeia
Sobre "Estrutura Não Linear"
Árvore
definição
Um elemento de dados pode ter de zero a um elemento predecessor imediato e dois ou mais elementos sucessores imediatos.
Uma árvore é um conjunto finito de n(n≥0) nós
A definição de uma árvore é recursiva. Existe apenas um nó denominado "raiz" e os nós restantes são chamados de "subárvores" do nó raiz.
estrutura lógica
Existe uma relação hierárquica entre os elementos
conceito básico
pais
O nó raiz do nó filho
criança
A raiz da subárvore de um nó é chamada de filho do nó.
irmão
Nós com os mesmos pais são irmãos um do outro
Nó da folha
Nó terminal, grau é 0
nó interno
Nó não terminal ou nó de ramificação, o grau não é 0
grau de nó
O número de subárvores de um nó
Nível do nó
A raiz está no nível 1, os filhos da raiz estão no nível 2 e assim por diante.
altura da árvore
O número máximo de camadas em uma árvore é registrado como a altura (ou profundidade) da árvore
Árvores ordenadas e não ordenadas
Se as subárvores dos nós da árvore estiverem ordenadas, é uma árvore ordenada, caso contrário, é um número não ordenado.
estrutura de armazenamento
representação dos pais
representação infantil
representação do irmão menor
Oferece a possibilidade de realizar a conversão entre árvores, árvores binárias e florestas.
Operações básicas
Atravessar
Caminho
Percurso raiz primeiro
Primeiro visite o nó raiz da árvore e, em seguida, percorra primeiro cada subárvore da raiz.
travessia de raiz traseira
Primeiro percorra cada subárvore da raiz em sequência e, em seguida, visite o nó raiz.
Outros segmentos
Árvore binária
definição
Uma árvore binária é um conjunto finito de n(n≥0) nós
A definição de uma árvore binária é recursiva. É composto por 1 nó raiz e 2 árvores binárias disjuntas chamadas subárvores esquerda e direita, respectivamente.
Propriedades principais
Existem no máximo 2 (i-1) nós de potência no i-ésimo nível (i≥1) da árvore binária
Uma árvore binária com altura k (k≥1) possui no máximo 2 k-1 nós.
Classificação
árvore binária completa
Não há nós vazios em cada camada
árvore binária completa
Exceto o último andar, todos os outros andares estão ocupados.
Os nós da última camada são colocados da esquerda para a direita e não podem ficar em branco.
árvore binária incompleta
estrutura de armazenamento
armazenamento sequencial
Armazene os nós da árvore binária em uma ordem apropriada em um conjunto de células de memória com endereços consecutivos.
Suponha uma árvore binária completa com o nó raiz número 1. Se houver um nó com o número i, então
Se i=1, então o nó é o nó raiz e não tem pais.
Se i> 1, então o nó pai deste nó é ⌊ i/2 ⌋
Se 2i≤n, então o filho esquerdo do nó é 2i, caso contrário não há filho esquerdo
Se 2i 1≤n, então o filho certo do nó é 2i 1, caso contrário não há filho certo
armazenamento em cadeia
armazenar
O nó contém elementos de dados, pais, a raiz da subárvore esquerda e a raiz da subárvore direita.
Lista vinculada binária disponível ou armazenamento de lista vinculada tripla
Operações básicas
Atravessar
definição
O processo de visitar cada nó da árvore de acordo com uma determinada estratégia e visitá-lo apenas uma vez
O processo de percorrer uma árvore binária é essencialmente um processo de organizar os nós da árvore em uma sequência linear de acordo com certas regras.
Caminho
(1) De acordo com a convenção de percorrer primeiro a subárvore esquerda e depois a subárvore direita, dependendo da localização do nó raiz visitado,
3 maneiras disponíveis
passagem de pré-encomenda
travessia em ordem
Travessia pós-ordem
(2) Travessia em ordem de camada (acesso de cima para baixo, da esquerda para a direita, camada por camada)
Outros segmentos
pista de árvore binária
definição
Nas informações de armazenamento dos nós da árvore binária, adicione informações do antecessor direto e do sucessor direto
árvore binária ideal
definição
Também conhecida como árvore de Huffman, é um tipo de árvore com o menor comprimento de caminho ponderado.
conceito básico
caminho
Um caminho de um nó para outro na árvore
comprimento do percurso
Número de ramificações no caminho
comprimento do caminho ponderado do nó
O comprimento do caminho do nó até a raiz da árvore multiplicado pelo peso do nó
comprimento do caminho da árvore
A soma dos comprimentos do caminho da raiz até cada folha
O comprimento do caminho ponderado da árvore
A soma dos comprimentos de caminho ponderados de todos os nós folhas da árvore
Algoritmo de construção
(1) No conjunto de árvores binárias, selecione as duas árvores com menor peso como subárvores esquerda e direita (aquela com menor peso das duas é colocada como subárvore esquerda) para construir uma nova árvore binária Os nós raiz. das subárvores esquerda e direita são A soma dos pesos dos pontos é usada como o peso do nó raiz da nova árvore binária; (2) Exclua essas duas árvores do conjunto e adicione a árvore recém-construída; Repita as etapas acima;
aplicativo
Codificação de Huffman
ilustrar
floresta
definição
Árvores e florestas são definidas mutuamente recursivamente
Operações básicas
Atravessar
Caminho
passagem de pré-encomenda
Primeiro visite o nó raiz da primeira árvore na floresta e, em seguida, atravesse primeiro a floresta de subárvores do nó raiz da primeira árvore. A última ordem atravessa a floresta de árvores restantes
travessia em ordem
Primeiro atravesse a floresta de subárvores da primeira árvore da floresta em ordem e, em seguida, visite o nó raiz da primeira árvore. Finalmente, em ordem atravessa a floresta composta pelas árvores restantes.
Conversão entre árvores, árvores binárias e florestas
Converter árvore em árvore binária
etapa
(1) Adicionar uma linha: Adicionar uma conexão entre nós irmãos
(2) Remoção de linha: O nó mantém apenas a conexão com o primeiro nó
(3) Ajuste de nível (rotação): Com o nó raiz da árvore como eixo, gire de modo que o primeiro nó filho fique localizado na posição filho esquerda e o nó irmão esteja localizado na posição filho direita.
Converter floresta em árvore binária
etapa
(1) Cada árvore da floresta é convertida em uma árvore binária
(2) A primeira árvore binária não se move e o nó raiz da próxima árvore binária é usado como filho direito do nó raiz da árvore binária anterior e conectado.
Converter árvore binária em árvore
etapa
(1) Adicione uma linha: n nós filhos direitos do filho esquerdo de um nó são todos nós filhos deste nó e conectados.
(2) Remoção de linha: Exclua as conexões entre todos os nós na árvore binária original e seus nós filhos certos
(3) Ajuste de nível (rotação)
Converter árvore binária em floresta
etapa
(1) Separe a árvore binária
Começando pelo nó raiz, exclua todas as conexões filhas corretas
(2) Converter árvore binária em árvore
foto
definição
Não há limite para o número de nós predecessores e nós sucessores de um nó.
Gráfico G(Gráfico) é uma tupla que consiste em conjuntos V(Vértice) e E(Edge), denotado como G=(V, E)
V é um conjunto finito não vazio de vértices (elementos de dados)
E é um conjunto finito de arestas (relações entre elementos de dados)
conceito básico
grau de vértice
Gastar
O número de arestas associadas ao vértice é a soma do grau de entrada e do grau de saída, denotado D (v)
grau
é o número de arestas direcionadas que terminam no vértice, registrado como ID (v)
grau fora
É o número de arestas direcionadas a partir deste vértice, registrado como OD(v)
caminho
Sequência de vértices do vértice vp ao vértice vq
comprimento do percurso
número no caminho
laço ou anel
O caminho onde o primeiro vértice e o último vértice são iguais
Se os vértices restantes do caminho forem diferentes, ele é chamado de caminho simples
subtrama
Gráficos conectados e componentes conectados
gráfico conectado
Quaisquer dois vértices são gráficos não direcionados conectados
componentes conectados
Subgrafo maximamente conectado deste gráfico
Gráfico fortemente conectado e componentes fortemente conectados
Gráfico fortemente conectado
Quaisquer dois vértices são gráficos direcionados conectados
Componentes fortemente conectados
Subgrafo maximamente conectado deste gráfico
líquido
Gráfico com pesos laterais
árvore direcionada
Um gráfico direcionado com um vértice tendo um grau de entrada de 0 e os vértices restantes tendo um grau de entrada de 1
árvore geradora
Subgrafo mínimo conectado do gráfico (sem ciclos)
A árvore geradora de um gráfico não é única
Caminho mais curto do ponto de origem único
Classificação
gráfico direcionado
Cada aresta tem uma direção
A relação entre vértices é representada por <vi, vj>
Isso significa que vi para vj tem uma aresta direcionada (também chamada de arco)
vi é o ponto inicial da aresta direcionada, chamada de cauda do arco
vj é o ponto final da aresta direcionada, chamado de cabeça do arco
Outros segmentos
gráfico acíclico direcionado
Gráfico direcionado sem ciclos
Gráfico não direcionado
Cada aresta não tem direção
A relação entre vértices é representada por (vi, vj)
gráfico completo
Cada vértice tem uma aresta com outros vértices
Classificação
Gráfico completo direcionado
gráfico completo não direcionado
estrutura de armazenamento
Notação de matriz de adjacência
Representação de lista vinculada de adjacência
Operações básicas
Atravessar
definição
A travessia do gráfico refere-se ao processo de partir de um determinado vértice e visitar todos os vértices do gráfico ao longo de um determinado caminho de pesquisa apenas uma vez.
Caminho
Primeira pesquisa em profundidade (DFS)
Pesquise e acesse primeiro a direção de profundidade, se possível
Amplitude da primeira pesquisa (BFS)
Pesquise primeiro na direção horizontal, se possível
Sobre a "Árvore Geradora Mínima"
definição
Para uma rede conectada, as arestas são ponderadas e cada aresta da árvore geradora também é ponderada.
A árvore geradora mínima é a árvore geradora com o menor peso
conceito básico
Árvore geradora à direita
A soma dos pesos de cada aresta da árvore geradora
Algoritmos de resolução de árvore geradora mínima comumente usados
Algoritmo de Prim
Algoritmo de Kruskal
Sobre "caminho mais curto de fonte única"
definição
Isso significa que dado um grafo direcionado ponderado G e um ponto de origem v0, encontre o caminho mais curto de v0 até os vértices restantes em G
Algoritmos de resolução comumente usados
Algoritmo de Dijkstra
Algoritmo de Floyd
aplicativo
Rede AOV (rede Activity On Vertex)
definição
Um gráfico direcionado que usa vértices para representar atividades e arestas direcionadas para representar relacionamentos prioritários entre atividades.
Os ciclos direcionados não devem aparecer na rede AOV
Verifique se existe um loop na rede AOV
método
Para um gráfico direcionado, construa uma sequência topologicamente ordenada de seus vértices. Se todos os vértices do gráfico estiverem em sua sequência topologicamente ordenada, não há ciclo.
etapa
(1) Selecione um vértice na rede com grau de entrada 0 e produza-o
(2) Exclua o vértice e todos os arcos associados da rede
(3) Repita as duas etapas acima até que não haja vértices com grau de entrada 0 na rede.
(4) Resultado
Se todos os vértices tiverem sido gerados, toda a classificação topológica será concluída, indicando que não há loop.
Se ainda houver vértices que não foram gerados e todos os vértices restantes tiverem vértices predecessores, a classificação topológica não poderá continuar neste momento, indicando que há um loop.
Rede AOE (rede Activity On Edge)
definição
Um gráfico direcionado no qual os eventos são representados por vértices, as atividades são representadas por arestas direcionadas e a duração da atividade é representada pelos pesos nas arestas.
O tempo necessário para todo o projeto é o comprimento do caminho mais longo do vértice inicial ao vértice final.
conceito básico
O evento representado pelo vértice é um sinal de que algumas atividades foram concluídas e algumas atividades podem ser iniciadas.
Fonte
O vértice inicial com indegree 0
ponto de encontro
Vértice final com grau externo 0
Caminho crítico
O caminho mais longo da fonte ao destino
Todas as atividades no caminho crítico são atividades críticas
A hora do evento de vértice
O primeiro tempo de ocorrência do evento de vértice ve(j)
O último horário de ocorrência do evento de vértice vl(i)
Operações em estruturas de dados
Encontrar
conceito básico
ilustrar
A pesquisa é uma operação básica comumente usada
tabela de pesquisa
Refere-se a uma coleção de elementos de dados (ou registros) do mesmo tipo
Palavras-chave
É o valor de um item de dados de um elemento de dados (ou registro)
Usado para identificar (identificar) este elemento de dados
palavra-chave primária
Uma palavra-chave que identifica exclusivamente um elemento de dados
palavras-chave secundárias
refere-se a uma palavra-chave que pode identificar vários elementos de dados
Procurar Resultados
Pesquisa bem-sucedida
Falha na pesquisa
duração média da pesquisa
O número esperado de vezes que o processo de pesquisa precisa ser comparado com o valor da palavra-chave fornecida
Operações básicas de tabelas de pesquisa
tabela de pesquisa estática
Consultar se um elemento de dados está na tabela de pesquisa
Recuperar vários atributos de um elemento de dados
tabela de pesquisa dinâmica
Insira um elemento de dados
Excluir um elemento de dados
Sobre "Tabela de pesquisa estática"
Encontrar método
Classificação
pesquisa sequencial
meia pesquisa
análise de processo
O processo de pesquisa pode ser descrito por uma árvore binária
Método de construção de árvore de decisão de pesquisa binária (binária)
(1) Tome o número da posição intermediária do intervalo de pesquisa atual como a raiz
(2) Os números de série dos registros na metade esquerda da subtabela e na metade direita da subtabela são usados como nós na subárvore esquerda e na subárvore direita da raiz, respectivamente.
Bloquear pesquisa
Sobre "Tabela de pesquisa dinâmica"
Características
A própria estrutura da tabela é gerada dinamicamente durante o processo de pesquisa
Classificação da estrutura da tabela
Árvore de classificação binária
definição
Também conhecida como árvore de pesquisa binária
pode ser uma árvore vazia
Ou uma árvore binária com as seguintes propriedades
Se a subárvore esquerda não estiver vazia, os valores de todos os nós na subárvore esquerda serão menores que o valor do nó raiz
Se a subárvore direita não estiver vazia, então os valores de todos os nós na subárvore direita são maiores que o valor do nó raiz
As próprias subárvores esquerda e direita são árvores classificadas binariamente.
árvore binária balanceada
definição
Também conhecida como árvore AVL
pode ser uma árvore vazia
Ou uma árvore binária com as seguintes propriedades
O valor absoluto da diferença entre as alturas das subárvores esquerda e direita não excede 1
As próprias subárvores esquerda e direita são árvores binárias balanceadas
operar
inserir
Tratamento de balanceamento unilateral tipo LL para a direita
Tratamento de balanceamento unilateral tipo RR para esquerda
Tipo LR primeiro processamento de equilíbrio de rotação bidirecional à esquerda e depois à direita
RL digite primeiro processamento de equilíbrio de rotação bidirecional à direita e depois à esquerda
B_tree de ordem m
definição
pode ser uma árvore vazia
Ou uma m-tree com as seguintes propriedades
Cada nó da árvore possui no máximo m subárvores
...
árvore vermelha preta
Tabela hash (ou tabela hash)
definição
O endereço de armazenamento do registro é obtido calculando uma função (chamada função hash) com a chave do registro como variável independente.
Ou seja, com base na função hash definida H (chave) e no método de tratamento de conflitos, um conjunto de palavras-chave é mapeado para um conjunto de endereços contínuo limitado (intervalo) e a "imagem" da palavra-chave no conjunto de endereços é usada como um local de armazenamento na tabela.
Este processo de mapeamento é chamado de hash ou hash
O local de armazenamento resultante é chamado de endereço hash ou endereço hash
conceito básico
Sobre colisões de hash
Para uma determinada função hash H e as duas chaves K1 e K2, se K1≠K2 e H(K1)=H(K2), é chamado de conflito
Palavras-chave com o mesmo valor de função hash são chamadas de sinônimos dessa função hash.
De um modo geral
As colisões só podem ser reduzidas tanto quanto possível, mas não completamente evitadas, porque a função hash é a imagem da palavra-chave definida para o conjunto de endereços
A função hash é uma imagem compactada e as colisões são inevitáveis
Principais questões a considerar
Como construir uma função hash
Métodos comuns
método de endereçamento direto
análise digital
Método Quadrado-Médio
método de dobramento
método de número aleatório
método de divisão deixando resto
Problemas que devem ser resolvidos
A função hash deve ser uma função de imagem compactada, que deve ter maior compactação para economizar espaço de armazenamento
A função hash deve ter boas propriedades de hash e mapear palavras-chave para várias unidades de armazenamento na área de armazenamento da maneira mais uniforme possível
Como resolver conflitos
Métodos comuns
método de endereçamento aberto
método de endereço de cadeia
refazer
Crie uma área pública de transbordamento
Operações básicas
Encontrar
conceito
Calcule o endereço de armazenamento do registro a ser verificado usando a mesma função hash e método de tratamento de conflitos usado ao armazenar elementos.
duração média da pesquisa
dependendo
Função hash
Como lidar com conflitos
Fator de preenchimento da tabela hash
Sobre o "Fator de preenchimento da tabela hash"
definição
α = número de registros carregados na tabela/comprimento da tabela hash
organizar
conceito básico
definição
Suponha que o conteúdo do arquivo contendo n registros seja {R1, R2,…,R} e as palavras-chave correspondentes sejam {k1,k2,…,kn}. Após a classificação, um arranjo {Rj1, Rj2,…,Rjn} é determinado, Faça com que suas palavras-chave satisfaçam a seguinte relação crescente (ou decrescente): kj1≤kj2≤...≤kjn (ou kj1≥kj2≥...≥kjn).
Estabilidade do método de classificação
Método de classificação estável
Registra Ri e Rj com a mesma palavra-chave, Ri está à frente de Rj. Após a classificação, a ordem de Ri e Rj permanece inalterada.
Método de classificação instável
Registra Ri e Rj com a mesma palavra-chave, Ri está à frente de Rj. Após a classificação, a ordem de Ri e Rj pode mudar
Operações básicas
(1) Compare o tamanho das palavras-chave;
(2) Dependendo do método de armazenamento, o local do registro pode precisar ser movido;
Classificação
Classificação interna
Classificação simples
classificação por inserção direta
Tipo de bolha
Ordenação por seleção simples
Tipo de colina
Classificação de pilha
Ordenação rápida
classificação por mesclagem
classificação de mesclagem bidirecional
Classificação de raiz
classificação externa
método básico
Classificação do método
fusão balanceada k-way
algoritmo
conceito básico
Pesquisa em teoria de algoritmos
Técnicas de design de algoritmo (/estratégia)
Responda à pergunta: “Como criar um algoritmo para resolver um problema específico?”
Técnicas de análise algorítmica
Responda à pergunta: “O algoritmo é bom o suficiente?”
definição
Algoritmo é uma descrição das etapas para resolver um problema específico. É uma sequência finita de instruções. Cada uma dessas instruções representa uma ou mais operações.
5 características importantes dos algoritmos
Finitude
certeza
viabilidade
digitar
saída
Sobre "Projeto de Algoritmo"
Técnica principal
Método de divisão e conquista, método de programação dinâmica, método ganancioso, método de retrocesso, método de ramificação e limite, algoritmo de probabilidade, algoritmo de aproximação
Sobre "Análise Algorítmica"
alguns critérios analíticos
Correção, confiabilidade, simplicidade e compreensibilidade do algoritmo
A complexidade de tempo e complexidade de espaço do algoritmo
Representação de algoritmo
linguagem natural
fluxograma
linguagem de programação
pseudo-código
Sobre "complexidade de tempo"
analisar
definição
Analisa principalmente o tempo de execução do algoritmo, ou seja, o número de operações básicas necessárias para a execução do algoritmo.
método
Estabeleça uma função T(n) com a escala de entrada n como variável independente para representar a complexidade de tempo do algoritmo.
De acordo com diferentes entradas, existem 3 situações
Melhor cenário possível
pior cenário
situação média
símbolo progressivo
é uma abstração adicional do método T(n) acima, que considera apenas a taxa de crescimento do tempo de execução (ou chamada de magnitude de crescimento)
Método Analítico
Ó marca
Análise assintótica do limite superior
exemplo:
Símbolo
Próxima análise gradual
Θ símbolo
Análise de limite superior assintótico e limite inferior assintótico, ou seja, análise de limite compacto assintótico
Estrutura do algoritmo
Geralmente pode ser dividido em
forma não recursiva
forma recursiva
Principais métodos de análise de complexidade de tempo
método de expansão
método de substituição
método de árvore recursiva
método principal
Algoritmo convencional
dividir e conquistar
Ideia básica
Decompor um grande problema que é difícil de resolver diretamente em uma série de problemas menores idênticos, para que possam ser decompostos individualmente, divididos e conquistados
recursão
Isso significa que a sub-rotina chama a si mesma direta ou indiretamente através de uma série de instruções de chamada.
Elementos básicos
Condições limite
Modo recursivo
Os principais passos
As etapas do algoritmo dividir e conquistar em cada nível de recursão
(1) Decomposição
(2) Resolver
(3) Mesclar
aplicativo
classificação por mesclagem
Máximo de campos e perguntas
programaçao dinamica
Ideia básica
Divida um grande problema que é difícil de resolver diretamente em uma série de problemas menores idênticos e ataque cada um deles. Ao contrário da abordagem de dividir para conquistar, os subproblemas muitas vezes não são independentes
Salve as respostas dos subproblemas resolvidos em uma tabela e recupere-as quando necessário
Os principais passos
(1) Descubra as propriedades da solução ótima
(2) Definir recursivamente o valor da solução ótima
(3) Calcule o valor ideal de baixo para cima
(4) Construa uma solução ótima com base nas informações obtidas ao calcular o valor ótimo
aplicativo
Problema de mochila 0-1
Subsequência comum mais longa (LCS)
método ganancioso
Ideia básica
A estratégia é fazer escolhas baseadas apenas nas informações atualmente disponíveis e obter soluções ótimas locais (/aproximadas).
forma de algoritmo
algoritmo ganancioso recursivo
algoritmo ganancioso iterativo
aplicativo
Problemas de seleção de atividades
problema de mochila
Retrocesso
Ideia básica
Depois de determinar a estrutura organizacional do espaço de solução, o método de retrocesso começa no nó inicial (nó raiz) e pesquisa todo o espaço de solução em profundidade. Até que a solução necessária seja encontrada ou não haja nós ativos no espaço de soluções
O objetivo da solução é encontrar todas as soluções que satisfaçam as restrições
espaço de solução
Deve conter pelo menos uma solução (ótima) para o problema
Geralmente expresso na forma de uma árvore ou gráfico
função delimitadora
Como o espaço de solução costuma ser muito grande, para uma pesquisa eficaz, alguns nós precisam ser podados durante o processo de pesquisa. Projete uma função delimitadora para o julgamento de poda (poda o mais cedo e tanto quanto possível)
Os principais passos
(1) Defina o espaço de solução do problema
(2) Determine a estrutura do espaço de solução que é fácil de pesquisar
(3) Pesquise o espaço de solução em profundidade
estrutura de pontuação
Maneira recursiva
não recursivo
aplicativo
Problema de mochila 0-1
n Problema da rainha
método branch e vinculado
Ideia básica
Semelhante ao método de retrocesso, é também um algoritmo que busca a solução do problema na árvore do espaço de soluções T do problema.
Pesquise o espaço da solução de maneira ampla ou com menor custo
O objetivo da solução é encontrar uma solução (ótima) que satisfaça as restrições
função delimitadora
Classificado de acordo com diferentes formas de selecionar o próximo nó de expansão da tabela de pontos ativos
Método de ramificação e limite em fila (FIFO, primeiro a entrar, primeiro a sair)
ramificação da fila de prioridade e método vinculado
Algoritmo probabilístico
Ideia básica
Quando o algoritmo executa determinadas etapas, você pode escolher aleatoriamente como proceder a seguir, permitindo que os resultados sejam errôneos com menor probabilidade e, à custa disso, obter uma redução substancial no tempo de execução do algoritmo.
Classificação
Algoritmo de Probabilidade Numérica
Algoritmo de Monte Carlo
Algoritmo de Las Vegas
Algoritmo de Sherwood
algoritmo de aproximação
Ideia básica
Desistir de buscar a solução ótima e substituir a solução ótima por uma solução ótima aproximada em troca da simplificação do projeto do algoritmo e da redução da complexidade do tempo
Medida de desempenho
A complexidade de tempo do algoritmo
O grau de aproximação da solução
algoritmo de mineração de dados
mineração de dados
conceito básico
É um assunto interdisciplinar que utiliza métodos de aprendizado de máquina para analisar e extrair uma variedade de dados (dados de banco de dados, dados de data warehouse, dados da Web, etc.)
essencial
é um algoritmo
A função principal
Classificação
retornar
Regras de associação
agrupamento
Algoritmo de otimização inteligente
Visão geral
Tecnologia de otimização
É uma tecnologia de aplicação baseada em matemática e usada para resolver soluções ótimas para diversos problemas de engenharia.
No campo da otimização, devido à intuitividade e ao mecanismo natural dessas construções de algoritmos, eles são frequentemente chamados de "algoritmos de otimização inteligentes" ou "algoritmos heurísticos modernos"
Algoritmos de otimização existentes
Rede Neural Artificial (RNA)
princípio
Um sistema dinâmico com uma topologia de gráfico direcionada que processa informações respondendo a estados de entrada contínuos ou descontínuos.
Classificação
Redes de feedforward e feedback
Classificação
Rede neural direta multicamadas baseada no algoritmo BP
aprendizado de máquina profundo
Redes de Crenças Profundas (DBNs)
Redes Neurais Convolucionais (CNNs)
algoritmo genético
Algoritmo de Recozimento Simulado (SA)
Algoritmo de Pesquisa Tabu (TS)
Algoritmo de Colônia de Formigas
Algoritmo de otimização de enxame de partículas (PSO)