Quando devemos construir árvores, gráficos para analisar um algoritmo?

Question

Em muitos algoritmos, é fácil entender como o algoritmo é executado, mas por que ele funciona bem e como ele pode trabalhar, não é muito fácil de ver, às vezes, os autores de construção de árvores ou grafos para colocar as coisas analisados-los e usar essas estruturas para descrever a propriedade do objeto de pesquisa e provar algumas propriedades das estruturas de finalmente dar uma explicação por que ele funciona bem...

Quando devemos usar árvores, gráficos para analisar um algoritmo?Ou equivalentemente, que a propriedade árvores ou grafos fazer bem ao descrever em teoria?

Como, em algoritmos de classificação, muitos algoritmos são analisados com uma árvore binária, em 2SAT algoritmos, o núcleo do problema é designada você pode encontrar um gráfico.

Bem, para os problemas com o modo fixo, as estruturas podem ser implícitas facilmente, como os problemas na OI ou leetcode, no entanto, na investigação, tal situação não é tão provável de acontecer.

Se, provavelmente, a melhor resposta é:bem, quando você sente que algumas estruturas são adequadas, você pode experimentá-los, é difícil dizer o que deve ser usado e o que não deve.Eu aceito isso.Estou ansioso para um mais inspirador resposta.

Answer 1

A resposta poderia ser como uma promo para estruturas de dados curso!

Você provavelmente estudou estruturas de dados no estudo de uma linguagem de programação, não de uma forma abstrata.

Você deve conhecer as principais características de uma estrutura de dados e o de ur problema para escolher o mais adequado para ele(pelo adequado, referimo-nos normalmente eficiente em tempo e espaço da complexidade das operações principais, e espero que muito significativo quero dizer, fácil de entender a representação)

Por exemplo u uso de BST se vc quiser fast search/inserir (O(n log n)), então u pode preferir AVL árvores se preocupar com o pior caso e pretende manter a árvore balanceada;preferem Hu-Tucker AVEIA, se vc acha que a diferença de frequência entre ur itens da pesquisa é considerável que tem um impacto sobre o desempenho.Árvores Huffman para a codificação, tabelas de hash se ur itens de r espalhados no intervalo e u quero fast search/inserção (const na av)....Árvores B, B+-árvores,...O mesmo vale para a escolha de aposta de matrizes, listas encadeadas, pilhas,....

Você pode ter um olhar para ele A arte da Programação de computadores, Vol 3 Pesquisa & Classificação

Então u pode mover-se em mais problemas práticos e que considere a natureza e as relações entre ur elementos.Escolha árvores se elas têm uma natureza Hierárquica, o gráfico se a ligação varia, e vértices ou arestas podem ter valores representam o custo ou lucro;às vezes, u pode repensar sobre ur escolha que dados para colocar vértices e arestas, neste caso u acho que o problema u r de problemas, e o desempenho dos conhecidos algoritmos u r indo para mapear em cada caso, para fazer ur escolha.

Espero que tenha sido útil

Answer 2

Não há uma rígida regra.Use-os se eles são úteis;não se eles não são.Como uma ampla orientação:

Gráficos geralmente são úteis quando você tem relacionamentos entre um par de itens.

As árvores são muitas vezes útil quando você tem uma relação hierárquica.