DataStructure And Algo
1.0.0
As estruturas de dados são um meio especializado de organizar e armazenar dados em computadores de forma que possamos executar operações nos dados armazenados com mais eficiência. As estruturas de dados têm um amplo e diversificado escopo de uso nos campos da ciência da computação e da engenharia de software. As estruturas de dados estão sendo usadas em quase todos os programas ou sistema de software que foram desenvolvidos. Além disso, as estruturas de dados estão sob os fundamentos da ciência da computação e da engenharia de software. É um tópico -chave quando se trata de perguntas sobre entrevistas de engenharia de software. Portanto, como desenvolvedores, devemos ter um bom conhecimento sobre estruturas de dados.
Uma matriz é uma estrutura de tamanho fixo, que pode conter itens do mesmo tipo de dados. Pode ser uma variedade de números inteiros, uma variedade de números de ponto flutuante, uma variedade de cordas ou mesmo uma matriz de matrizes (como matrizes bidimensionais). As matrizes são indexadas, o que significa que o acesso aleatório é possível.
Inserir elementos em uma matriz e excluir elementos de uma matriz não pode ser feita imediatamente, pois as matrizes são fixadas em tamanho. Se você deseja inserir um elemento em uma matriz, primeiro precisará criar uma nova matriz com o tamanho aumentado (tamanho atual + 1), copie os elementos existentes e adicione o novo elemento. O mesmo vale para a exclusão com uma nova variedade de tamanho reduzido.
Uma lista vinculada é uma estrutura seqüencial que consiste em uma sequência de itens em ordem linear que estão vinculados um ao outro. Portanto, você deve acessar dados sequencialmente e o acesso aleatório não é possível. As listas vinculadas fornecem uma representação simples e flexível de conjuntos dinâmicos.
Uma pilha é uma estrutura LIFO (a última vez em primeiro lugar - o elemento colocado finalmente pode ser acessado a princípio) que pode ser comumente encontrado em muitas linguagens de programação. Essa estrutura é nomeada como "pilha" porque se assemelha a uma pilha do mundo real-uma pilha de placas.
Usado para avaliação da expressão (por exemplo: um algoritmo de pátio de manobra para analisar e avaliar expressões matemáticas). Usado para implementar chamadas de função na programação de recursão.
Uma fila é uma estrutura FIFO (primeiro a partir da primeira vez - o elemento colocado a princípio pode ser acessado a princípio) que pode ser comumente encontrado em muitas linguagens de programação. Essa estrutura é nomeada como "fila" porque se assemelha a uma fila do mundo real-pessoas esperando em uma fila.
Usado para gerenciar threads no multithreading. Usado para implementar sistemas de fila (por exemplo: filas prioritárias).
Uma tabela de hash é uma estrutura de dados que armazena valores com chaves associadas a cada uma delas. Além disso, ele suporta a pesquisa com eficiência se soubermos a chave associada ao valor. Portanto, é muito eficiente na inserção e pesquisa, independentemente do tamanho dos dados.
O endereço direto usa o mapeamento individual entre os valores e as teclas ao armazenar em uma tabela. No entanto, há um problema com essa abordagem quando há um grande número de pares de valor-chave. A tabela será enorme com tantos registros e pode ser impraticável ou até impossível de ser armazenada, dada a memória disponível em um computador típico. Para evitar esse problema, usamos tabelas de hash .
Uma função especial denominada função hash (h) é usada para superar o problema acima mencionado no endereçamento direto. No acesso direto, um valor com a chave K é armazenado no slot k. Usando a função hash, calculamos o índice da tabela (slot) para o qual cada valor vai. O valor calculado usando a função de hash para uma determinada chave é chamado de valor de hash que indica o índice da tabela para a qual o valor é mapeado.
Uma árvore é uma estrutura hierárquica em que os dados são organizados hierarquicamente e estão ligados. Essa estrutura é diferente de uma lista vinculada, enquanto, em uma lista vinculada, os itens são vinculados em um pedido linear. Vários tipos de árvores foram desenvolvidos ao longo das últimas décadas, a fim de atender a certas aplicações e atender a certas restrições. Alguns exemplos são árvores de busca binária, árvore B, Treap, árvore-preta vermelha, árvore sply, árvore AVL e árvore n-ara.
Uma árvore de pesquisa binária (BST), como o nome sugere, é uma árvore binária onde os dados são organizados em uma estrutura hierárquica. Essa estrutura de dados armazena valores em ordem classificada. Cada nó em uma árvore de pesquisa binária compreende os seguintes atributos.
Uma árvore de busca binária exibe uma propriedade única que a distingue de outras árvores. Esta propriedade é conhecida como a propriedade ** Binária-Pesquisa-Tree **.
Uma pilha é um caso especial de uma árvore binária, onde os nós pais são comparados aos seus filhos com seus valores e são organizados de acordo.
Os montes podem ser de 2 tipos.
Um gráfico consiste em um conjunto finito de vértices ou nós e um conjunto de bordas que conectam esses vértices.
A ordem de um gráfico é o número de vértices no gráfico. O tamanho de um gráfico é o número de arestas no gráfico.
Diz -se que dois nós são adjacentes se estiverem conectados entre si pela mesma borda.
Diz -se que um gráfico G é um gráfico direcionado se todas as suas bordas tiverem uma direção indicando qual é o vértice inicial e qual é o vértice final . Dizemos que (u, v) é um incidente ou deixa o vértice u e é incidente ou entra no vértice v. Auto-loops: bordas de um vértice para si.
Diz -se que um gráfico G é um gráfico não direcionado se todas as suas bordas não tiverem direção. Pode ser entre os dois vértices.
Se um vértice não estiver conectado a nenhum outro nó no gráfico, é considerado isolado .
Um trie é uma estrutura de dados de recuperação de informações semelhantes a árvores cujos nós armazenam as letras de um alfabeto. Também é conhecido como uma árvore digital ou uma árvore de radix ou árvore prefixo.
Trie é uma estrutura de dados de recuperação de informações eficiente. Usando o TRIE, as complexidades de pesquisa podem ser levadas ao limite ideal (comprimento da chave). Se armazenarmos as teclas na árvore de pesquisa binária, um BST bem equilibrado precisará de tempo proporcional a M * log n, onde M é o comprimento máximo da corda e N é o número de chaves na árvore. Usando o Trie, podemos pesquisar a chave no tempo o (m) .
1. Trie padrão : é uma árvore ordenada como estrutura de dados.
2. Trie comprimido : é usado para obter otimização de espaço. Um trie compactado é uma versão avançada do Trie padrão.
3. Trie de sufixo : Um trie de sufixo é uma versão avançada do trie comprimido.
Com Trie, podemos inserir e encontrar strings no tempo O (l) em que l representa o comprimento de uma única palavra. Isso é obviamente mais rápido que o BST. Isso também é mais rápido que o hash por causa das maneiras pelas quais é implementado. Não precisamos calcular qualquer função de hash. Outra vantagem do trie é que podemos imprimir facilmente todas as palavras em ordem alfabética, o que não é facilmente possível com o hash.
A programação dinâmica é uma técnica que divide os problemas em subproblemas e salva o resultado para fins futuros, para que não precisemos calcular o resultado novamente. Os subproblemas são otimizados para otimizar a solução geral é conhecida como propriedade ideal da subestrutura. O principal uso da programação dinâmica é resolver problemas de otimização. Aqui, os problemas de otimização significam que, quando estamos tentando descobrir o mínimo ou a solução máxima de um problema. A programação dinâmica garante encontrar a solução ideal de um problema se a solução existir.
Algoritmo de complexidade do tempo O (1) Procurando um elemento específico em uma matriz, como esta, por exemplo: print (my_array [97]), independentemente do tamanho da matriz, um elemento pode ser analisado diretamente, apenas requer uma operação. (Isso não é realmente um algoritmo, mas pode nos ajudar a entender como a complexidade do tempo funciona.)
O (n) encontrando o menor valor. O algoritmo deve executar operações em uma matriz com n valores para encontrar o menor valor, porque o algoritmo deve comparar cada valor uma vez.
O (n 2) Corrente de bolhas, classificação de seleção e classificação de inserção são algoritmos com essa complexidade de tempo. A razão de suas complexidades de tempo é explicada nas páginas para esses algoritmos.
Grandes conjuntos de dados diminuem significativamente esses algoritmos. Com apenas um aumento em n de 100 a 200 valores, o número de operações pode aumentar em até 30000!
O (n log n) O algoritmo do QuickSort é mais rápido em média do que os três algoritmos de classificação mencionados acima, com o O (n log n) sendo a média e não o pior dos casos. Na pior das hipóteses, o tempo para o QuickSort também é O (n 2), mas é o tempo médio que torna o Quicksort tão interessante. Vamos aprender sobre o Quicksort mais tarde.
A referência é retirada deste link - Sourav Saini?
