Conecte-se
Fazer login

Galeria de mapas mentais Capítulo Um Introdução

Capítulo Um Introdução

Um artigo sobre mapas mentais de estrutura de dados, conceitos básicos de estruturas de dados, algoritmos e avaliação de algoritmos, etc. Espero que isto ajude!

Editado em 2023-11-21 17:17:08

WSb6eYgD

Trabalhos recentes Ver mais trabalhos>>

Anévrisme intracrânien
Il s'agit d'une carte mentale sur les anévrismes intracrâniens, avec le contenu principal, notamment: le congé, l'évaluation d'admission, les mesures infirmières, les mesures de traitement, les examens auxiliaires, les manifestations cliniques et les définitions.
Entretien de la comptabilité des coûts
Il s'agit d'une carte mentale sur l'entretien de comptabilité des coûts, le principal contenu comprend: 5. Liste des questions d'entrevue recommandées, 4. Compétences de base pour améliorer le taux de réussite, 3. Questions professionnelles, 2. Questions et réponses de simulation de scénarios, 1. Questions et réponses de capacité professionnelle.
Méthode de recherche de littérature
Il s'agit d'une carte mentale sur les méthodes de recherche de la littérature, et son contenu principal comprend: 5. Méthode complète, 4. Méthode de traçabilité, 3. Méthode de vérification des points, 2. Méthode de recherche inversée, 1. Méthode de recherche durable.

Capítulo Um Introdução

WSb6eYgD

Trabalhos recentes Ver mais trabalhos>>

Recomendado para você
Descrição

"Características e Funções do SGBD na Gestão de Bancos de Dados"
- 4
livia.morais@aluno.unifenas.br
Noções básicas comuns de computador
- 10
WSb6eYgD
01Estrutura de dados
- 11
WSysQn6v
Dados e estruturas de dados
- 16
슈퍼직장인
Mapa mental de algoritmo de estrutura de dados
- 9
WSCoUtCI
algoritmo de classificação de estrutura de dados
- 11
WSCoUtCI
Algoritmo de pesquisa de estrutura de dados
- 14
WSCoUtCI
Estruturas de dados e algoritmos
- 14
WSCoUtCI
Implementação de estrutura de dados e análise de algoritmo
- 9
WSCoUtCI
estrutura de dados
- 18
WSCoUtCI

Capítulo Um Introdução

1.1 Conceitos básicos de estrutura de dados

Conceitos básicos e terminologia

1. Dados

O conjunto de todos os símbolos que podem ser inseridos em um computador e reconhecidos e processados por um programa de computador

Todos os dados são representados no computador como binários

2. Elementos de dados

Os elementos de dados são as unidades básicas de dados e geralmente são considerados e processados como um todo

3. Itens de dados

Os elementos de dados são compostos por vários itens de dados, que são as menores unidades indivisíveis de dados.

4. Objetos de dados

Um objeto de dados é uma coleção de elementos de dados com as mesmas propriedades

5. Tipo de dados

Um tipo de dados é uma coleção de valores e um conjunto de operações definidas nesta coleção.

Classificação

Tipo atômico

Tipos de dados cujos valores não são divisíveis

Por exemplo: int

tipo de estrutura

Tipos de dados cujos valores podem ser subdivididos

Por exemplo: estrutura

Tipo de dados abstrato (ADT)

D: objeto de dados

S: relacionamento de dados

P: Operações básicas

Três elementos da estrutura de dados

1. Estrutura lógica dos dados

definição

Uma coleção de elementos de dados que possuem um ou mais relacionamentos específicos entre si

Classificação

estrutura linear

relacionamento um a um

Características

Exceto o primeiro elemento, todos os outros elementos possuem apenas um "predecessor direto"

Exceto o último elemento, todos os outros elementos têm um "sucessor direto" único

juntar

Pertencem ao mesmo conjunto

Árvore

relacionamento um-para-muitos

Características

Exceto o nó raiz, todos os outros pontos possuem apenas um "predecessor direto"

Exceto os nós folha, todos os outros elementos têm vários “sucessores diretos”

grade (Estrutura gráfica)

relacionamento muitos-para-muitos

Características

Para qualquer vértice, pode haver vários “predecessores diretos” e “sucessores diretos”

2. Estrutura física dos dados (estrutura de armazenamento)

definição

Estrutura de armazenamento refere-se à representação da estrutura de dados no computador (também chamada de imagem), também chamada de estrutura física

Classificação

estrutura de armazenamento sequencial

definição

Armazene nós logicamente adjacentes em unidades de armazenamento fisicamente adjacentes.

Geralmente representado por uma matriz

vantagem

O acesso aleatório pode ser alcançado

Cada elemento ocupa menos espaço

deficiência

Apenas um bloco adjacente inteiro de espaço de armazenamento pode ser usado, o que é propenso à fragmentação.

Ilustração

estrutura de armazenamento em cadeia

definição

Não é necessário que elementos logicamente adjacentes também sejam fisicamente adjacentes.

Use ponteiros para representar relacionamentos lógicos entre elementos

vantagem

Aproveite ao máximo todo o espaço de armazenamento

deficiência

Apenas acesso sequencial

Os ponteiros ocupam espaço de armazenamento adicional

ilustrar

Endereço da unidade de armazenamento dentro do nó: deve ser contínuo

Endereços de unidades de armazenamento entre nós: não necessariamente consecutivos

Ilustração

Estrutura de armazenamento de índice

definição

Ao armazenar informações dos elementos de dados, uma tabela de índice também é criada.

A forma geral é: <palavra-chave, endereço>

vantagem

Recuperação rápida

deficiência

As tabelas de índice ocupam espaço de armazenamento adicional

Ao adicionar ou excluir dados, você precisa modificar a tabela de índice

Estrutura de armazenamento de hash

definição

Calcule o endereço do elemento de dados diretamente com base no tamanho da palavra-chave

Também conhecido como armazenamento de hash

vantagem

Recuperar, adicionar e excluir nós é rápido

deficiência

Se a função hash não for boa, ocorrerão conflitos de armazenamento e a resolução de conflitos aumentará a sobrecarga de tempo e espaço.

estrutura de armazenamento não sequencial

3. Operações de dados

definição

As operações aplicadas aos dados incluem a definição e implementação das operações.

As operações são definidas para estruturas lógicas

A implantação da operação é baseada na estrutura física

1.2 Algoritmos e avaliação de algoritmos

Conceitos básicos de algoritmos

Fórmula de valor = algoritmo de estrutura de dados = programa

1. Definição de algoritmo

É uma descrição das etapas para resolver um problema específico. É uma sequência finita de instruções, onde cada instrução representa uma ou mais operações.

2. Método de descrição do algoritmo

linguagem natural

fluxograma

pseudo-código

linguagem de programação

3. Cinco características dos algoritmos

(1) Finitude

Termina após a execução de etapas finitas, e cada etapa pode ser concluída em tempo finito

Por exemplo: código de programa de loop infinito

(2) Certeza

Cada instrução deve ter um significado exato para que não haja ambigüidade na compreensão do leitor.

Apenas a mesma saída pode ser obtida para a mesma entrada

(3) Viabilidade

As operações descritas no algoritmo podem ser realizadas executando as operações básicas um número limitado de vezes.

(4)Entrada

Um algoritmo tem zero ou mais entradas

(5)Saída

Um algoritmo tem uma ou mais saídas

4. Avaliação de algoritmos

(1) Correção

Algoritmos resolvem problemas corretamente

O nível “certo”

a. O programa não contém erros gramaticais.

b. Para diversas combinações de dados de entrada do método, podem ser produzidos resultados de saída que atendam aos requisitos.

c. Capaz de produzir resultados que atendam aos requisitos para dados de entrada ilegais

d. Para todos os dados de entrada legais, podem ser produzidos resultados de saída que atendam aos requisitos.

(2) Legibilidade

Ajude as pessoas a entender o algoritmo

(3) Robustez

Os algoritmos também podem reagir ou processar adequadamente quando os dados de entrada são ilegais

(4) Alta eficiência e baixos requisitos de armazenamento

Eficiência se refere ao tempo que leva para um algoritmo ser executado

Os requisitos de armazenamento referem-se ao espaço máximo de armazenamento necessário durante a execução do algoritmo.

Métricas de Algoritmos

Métricas

complexidade de tempo

complexidade do espaço

Método de medição

Estatísticas pós-evento

Use um cronômetro de computador para cronometrar o tempo de execução do programa no computador

deficiência

(1) O programa compilado com base no algoritmo deve ser executado primeiro

(2) O tempo de execução resultante depende de fatores ambientais, como hardware e software de computador.

(3) O custo de execução do programa é relativamente alto

Pré-análise e estimativa

Antes da programação de computadores, os algoritmos são estimados com base em métodos estatísticos

O tempo necessário para a execução depende

(1) Qual estratégia o algoritmo deve escolher?

(2) Escala do problema

(3) Linguagem para escrever programas

(4) A qualidade do código de máquina gerado pela compilação

(5) A velocidade com que a máquina executa instruções

ponto de foco

Deixando de lado fatores relacionados a hardware e software de computador, pode-se considerar que o tamanho da “carga de trabalho em execução” de um algoritmo específico depende apenas do tamanho do problema (n), ou seja, é uma função do tamanho do problema.

complexidade de tempo

Método de cálculo

Frequência de frase

O número de vezes que a operação original é executada na instrução dentro do loop mais profundo

representação de função

De modo geral, o número de vezes que as operações básicas do algoritmo são repetidas é uma função f(n) do tamanho do problema n, e a medição do tempo do algoritmo é registrada como T(n)=O(f(n)) (complexidade de tempo)

ponto de foco

Olhe apenas para o nível mais alto

Remova o termo constante

ignorar coeficiente

Relacionamento comum de tamanho O(n)

três condições

melhor complexidade de tempo

Pior complexidade de tempo

complexidade média de tempo

Fatores de influência

estado inicial dos dados

Tamanho do problema

complexidade do espaço

Método de cálculo

A complexidade espacial do algoritmo é registrada como S(n)=O(f(n))

ponto de foco

Analise o espaço extra além da entrada e do programa