Encontrar el big O de esta función que escribí para imprimir todas las palabras en un trie.
Hice este trie:
class Trie:
def __init__(self):
self.root = {}
self.end = '\0'
def add(self,text):
node = self.root
for letter in text:
if letter in node:
node = node[letter]
else:
node[letter]={}
node = node[letter]
node[self.end] = True
def addAll(self,lst):
for word in lst:
self.add(word)
Y creé esta función para imprimir todas las palabras del trie:
def printWords(root,word=""):
if root==True:
print(word[:-1])
return
for letter in root:
printWords(root[letter],word+letter)
¿Cómo puedo encontrar el big O de esta función printWords?
davy.ai
El O grande de la función
printWordses O(n), donde n es el número total de nodos en el trie. Esto se debe a que la función visita recursivamente cada nodo en el trie exactamente una vez, y el número de nodos en un trie es proporcional al número total de caracteres en todas las palabras que se han agregado al trie. Por lo tanto, el tiempo de ejecución de la función es directamente proporcional al tamaño de los datos de entrada, es decir O(n).