Ferramentas de Site


algoritmo:tries

Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

Links para esta vista de comparação

Ambos os lados da revisão anterior Revisão anterior
Próxima revisão
Revisão anterior
algoritmo:tries [2012/12/28 10:48]
127.0.0.1 Edição externa
algoritmo:tries [2021/05/13 10:23] (Atual)
Linha 1: Linha 1:
-====== Tries estrutura de dados para armazenar Strings ======+====== Triesestrutura de dados para armazenar Strings ======
  
-Ora bem, hoje trago-vos uma estrutura de dados para armazenar strings mais propriamente. Tem a vantagem de ser __muito__ rápida e de ter a capacidade de partilhar posições das strings que queremos guardar, sendo assim eficiente também a nível de memória.+As Tries são uma estrutura de dados para armazenar strings. Tem a vantagem de ser __muito__ rápida e de ter a capacidade de partilhar posições das strings que queremos guardar, sendo assim eficiente também a nível de memória.
  
-Basicamente em cada nó vamos ter em cada nó um vector de ponteiros que vai ser o nosso "abecedário", ou seja, poderá ter, por exemplo, 26 posições. Se determinada letra existir na string a partir de determinado nó criámos uma nova estrutura do mesmo tipo da anterior.+Basicamente vamos ter em cada nó um vector de ponteiros que vai ser o nosso "abecedário", ou seja, poderá ter, por exemplo, 26 posições. Se determinada letra existir na string a partir de determinado nó, criamos uma nova estrutura do mesmo tipo da anterior.
  
-No final da string marcámos numa flag que é mesmo o final da string para não existirem problemas na pesquisa de strings.+No final da string marcamos numa flag que é mesmo o final da string para não existirem problemas na pesquisa de strings.
  
 **Complexidade:** **Complexidade:**
-  * Inserção de uma string: <m>O(Len).</m> Len = tamanho da string.+  * Inserção de uma string: <m>O(Len)</m>Len = tamanho da string.
   * Procurar string: <m>O(Len)</m>. Len = tamanho da string.   * Procurar string: <m>O(Len)</m>. Len = tamanho da string.
  
-A partir daqui já podemos ver que a complexidade é muito boa visto que se guardássemos as strings num vector (como se costuma fazer) teríamos uma complexidade de <m>O(n * len)</m> em que n é o número de strings e len é o tamanho máximo de cada string - temos que percorrer todas as strings e comparar uma a uma com a que queremos encontrar.+A partir daqui já podemos ver que a complexidade é muito boa visto que se guardássemos as strings num vectorteríamos uma complexidade de <m>O(n * len)</m> em que n é o número de strings e len é o tamanho máximo de cada string - temos que percorrer todas as strings e comparar uma a uma com a que queremos encontrar.
  
 Vou deixar aqui uma imagem com a estrutura. Vou deixar aqui uma imagem com a estrutura.
-{{ :c:alg_tries.png |Estrutura Tries}}+{{ :algoritmo:alg_tries.png |Estrutura Tries}}
 [[http://www.topcoder.com/i/education/alg_tries.png]] [[http://www.topcoder.com/i/education/alg_tries.png]]
  
Linha 90: Linha 90:
  {  {
  if (find_word (input, head) == true)   if (find_word (input, head) == true) 
- printf ("String found!n");+ printf ("String found!\n");
   
  else   else 
- printf ("String not found!n");+ printf ("String not found!\n");
   
  scanf ("%s", input);  scanf ("%s", input);
Linha 102: Linha 102:
  
 {{tag>cpp}} {{tag>cpp}}
 +
algoritmo/tries.1356691714.txt.gz · Última modificação em: 2018/05/14 21:37 (edição externa)