-
Calculando a altura da árvore (que são potências de 2), você consegue descobrir qual seria o número máximo de comparações, uma vez que no pior caso, a busca por uma palavra iniciaria na raiz e finalizaria numa folha.
-
O caminho maximo seria uma lista simplesmente encadeada, partindo da raiz ate a folha, e essa lista seria do tamanho da altura da arvore.
Como a altura da arvore binaria é log x (base 2), onde X é o numero de elementos, e 2 por se tratar a uma arvore binaria balanceada (ou seja, de tamanho minimo).
Pela formula:
Log (numero de palavras) ( base 2) = X
Sacanagem alguem fazer essa conta numa prova dessas, mas 2^22 = 4194304 (4 milhoes aproximadamente) => X = 22;
Ja 2^23 seria 8388608 (8 milhoes, notem como uma unidade faz a diferenca)
E o tipo de percursos, falou em ordem alfabetica, é in-oder ou em-ordem, como o proprio nome ja diz. Heheheh!!
-
A questão seria muito fácil se não colocassem para calcular 2^22 e 2^23. Meu cérebro ainda não gravou todas as potências de 2. Algúem bom em matemática, sabe algum macete para gravar a potência de 2?
-
Para lembrar potencia de 2 fácil: 2 ** 10 = 1k (1024)
2** 20 = 1 mega2 ** 30 = 1 giga .. e assim por diante
-
Normalmente, a FCC apresenta 2 alternativas bastante similares para questões como essa. Por exemplo, 22 em-ordem e 23 em-ordem. A chance de a resposta estar em uma das duas é bastante alta. Observe que as outras alternativas já são mais "descoladas" dessas duas...
1 - MÉTODO DE PESQUISA:
A altura da árvore binaria é log(base 2)x, onde:
x = número de elementos
base 2 por se tratar a uma arvore bináriabalanceada (ou seja, de tamanho mínimo)
log(base 2) x = 4.000.000
2^x = 4.000.000 (a qual potência devemos elevar o algarismo 2 para obtermos 4.000.000?)
2^1 = 2
2^10 = 1024
2^11 = 2048
2^12 = 4096
2^20 ~ 1024000
2^21 ~ 2048000
2^22 ~ 4096000 ~ 4 milhões
x = 22
2 - MÉTODO DE ORDENAÇÃO:
Como a proposta é obter as palavras emordem alfabética, o tipo de recurso na árvore que permite a recuperação éin-order ou em-ordem.
-
Lembrando apenas que é (2^x) -1. Então com 22 buscas você consegue até 4.194.303 palavras e não 4.194.304. Também na prática é custoso em termos de processamento obter uma árvore 100% balanceada, normalmente se usam algoritmos que apenas limitam o desbalanceamento como AVL ou Red-Black.
-
A resposta é log n onde n é 4.000.000, ou seja, qual a potência de 2 cujo resultado é 4.000.000?
Se 2^10 = 1024 (todo mundo sabe porque corresponde a quantidade de bytes em 1Kbyte)
2^20 = 1024 X 1024 = 1.048.576
2^22 = 1.048.576 X 4 = 4.194.304 (4 milhoes aproximadamente). Resposta: 22
-
Força Guerreiro!!!!!!