Jump to content

Como calcular o espaço em memória duma trie??


nellaf
 Share

Recommended Posts

Boas pessoal

Tenho uma trie {0...9} coma as chaves "12340", "2340", 12403, "123405" e queria saber como calculo o espaço necessário oara representar essa trie com essas mesmas chaves?

E como faço uma função em c para esse efeito  cconsiderando que um int ocupa 4 bytes e um apontador para qualquer tipo também ocupa 4 bytes, pode ser em pseudo-código só para ter uma ideia?

Muito obrigado

Link to comment
Share on other sites

Em worst case terás uma complexidade de espaço de O(N*M) em que N é a quantidade se strings ou chaves a inserir e M é o tamanho de todas essas strings.

Quanto à outra parte do post não percebi.

Na primeira pergunta, o que pergunto era saber quanta ocupa em bytes essa trie em memória, por exemplo, em memória poderia ser 80 bytes.

Quanto a segunda pergunta, queria saber como faço em c esse mesmo calculo com a informação apresentada...

Obrigado

Link to comment
Share on other sites

O que é que já tentaste? Qual é a tua abordagem ao problema e onde é que achas que ela falha? Em suma, qual é a dúvida?

Pelas minhas contas os int's ocupam 84 bytes, mas ainda falta calcular os apontadores que não sei quais hei-de contar....

Alguém me pode mostrar como calcular??

Link to comment
Share on other sites

Faz qq coisa do género:

Uma recursão que tira a casa das dezenas de cada um dos números do conjunto, ordena e chama-se com um subconjunto que tem os elementos que têm o mesmo número das dezenas. Vais fazendo as contas pelo meio.

Pegando no teu exemplo ("12340", "2340", 12403, "123405"), no inicio o conjunto é composto por todos os elementos, logo ficas com um vector <0, 0, 3, 5>. Vais ter um ponteiro por cada número, logo neste caso, vão ser 3. Chamas a função recursivamente com os valores <1234, 234>, cujo os números das dezenas ordenados dão <4, 4>, logo mais um ponteiro. Chamas com <123, 23> e por aí adiante.

A optimização mais óbvia é não fazeres a recursão quando o subconjunto a analisar tem só um membro. Fazes logo as contas (log 10).

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.