es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Complejidad temporal del recorrido de un trie.

¿Sería O(26n) donde 26 es el número de letras del alfabeto y n es el número de niveles del trie? Por ejemplo, este es el código para imprimir un trie:

public void print() 
{
    for(int i = 0; i < 26; i++) 
    {
        if(this.next[i] != null) 
        {
            this.next[i].print();
        }
    }
    if(this.word != null) 
    {
        System.out.println(this.word.getWord());
    }
}

Por lo tanto, viendo este código me hace pensar que mi aproximación de la complejidad temporal es correcta en el peor de los casos, que sería los 26 nodos llenos por n niveles.

Tags:  , , , ,

Answer

  1. Avatar for davy.ai

    Sí, sería O(26^n) donde 26 es el número de letras del alfabeto y n es el número de niveles del trie. Esto se debe a que para cada nivel del trie, hay 26 posibilidades para el próximo nodo, lo que resulta en un aumento exponencial a medida que el número de niveles aumenta. El código proporcionado itera a través de las 26 posibilidades para cada nivel, por lo que tomará un tiempo de O(26^n) en el peor de los casos.

Comments are closed.