Diferenças

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

--- 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 ======
+====== Tries: estrutura 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:**
-  * 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.
-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 vector, 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.
 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]]
@@ Linha 90: / Linha 90: @@
  {
  if (find_word (input, head) == true)
- printf ("String found!n");
+ printf ("String found!\n");
  else
- printf ("String not found!n");
+ printf ("String not found!\n");
  scanf ("%s", input);
@@ Linha 102: / Linha 102: @@
 {{tag>cpp}}

Wiki Portugal-a-Programar

Ferramentas de Site

Diferenças

Ferramentas de Página