Recibí el siguiente problema (sopa de letras) como ejercicio de mi curso de estructura de datos.
https://github.com/kennedyCzar/AlphabetSoup-Using-Django
Lo resolví en O(m+s) donde m es la longitud del mensaje y s es la longitud de la sopa (acabo de crear una tabla a partir de la sopa y decidí si el mensaje se puede crear o no usando esa tabla)
def checkBowl(message, soup):
d = {}
# O(S)
for c in soup:
d[c] = d.get(c, 0) + 1
# O(m)
for c in message:
if(d.get(c, 0) == 0):
return False
else:
d[c] -= 1
# So the overall time complexity is O(m+s)
return True
pero parece que el GitHub dado lo resolvió en O(mlogm), sin embargo, creo que su solución está en O(m*s) porque simplemente no consideró que el operador in de Python funciona en O(longitud del lista).
Por cierto, ¿alguien puede darnos una pista? ¿Es posible resolver este problema con una mayor complejidad temporal? (el problema especificaba que el plato de sopa puede ser muy grande)
------------------------------------
Como dijiste, el algoritmo vinculado, para cada letra del mensaje, itera sobre la sopa para encontrar la letra. Si se encuentra la carta, se retira de la sopa. Por tanto, la complejidad del tiempo es O(m * S).
Tu algoritmo es O(m + S) porque iteras solo una vez sobre la sopa. Entonces tu solución es mejor.
Pero ¿y si la sopa es muy grande? ¿Qué tal una sopa infinita? Si la sopa es un generador infinito, nunca terminarás de construir tu diccionario aunque las primeras letras de la sopa sean el mensaje en sí.
Esto nos lleva a una idea: ¿por qué no repetir las letras de la sopa hasta obtener las letras del mensaje? En este caso, ustedLeerá las letras hasta que pueda escribir el mensaje y se detendrá tan pronto como se complete el mensaje:
import collections
def check_bowl2(message, soup):
# O(m)
message_letters = collections.Counter(message)
# O(S)
for c in soup:
if c not in message_letters: # we don't need `c`
pass
elif message_letters[c] == 1:
del message_letters[c] # we won't need `c` anymore
if not message_letters: # we found all letters
return True
else: # we still need `c`, but one less time
message_letters[c] -= 1
return False
La complejidad temporal sigue siendo O(m + S), pero la complejidad espacial se reduce: O(m) frente a O(S). Por supuesto, si buscas muchos mensajes en la misma sopa, crear el dictado sigue siendo la mejor opción.
No creo que encuentres un algoritmo más rápido que O(S): en el peor de los casos (el mensaje está ausente), tienes que iterar sobre toda la sopa al menos una vez.
2
Sí, como mencioné la pregunta says "Puede ser un plato de sopa muy grande que contiene muchas letras" y tu solución de alguna manera resuelve eso. pero, ¿acceder al diccionario O(1) u O(n) es en el peor de los casos? Quiero decir, como @TUI lover mencionó que el peor caso es O(n), por lo que la complejidad sería O(mS), ¿verdad?
Yo.
29 de marzo de 2021 a las 8:47
1
Como dijo @TUI lover, el peor de los casos es O(n) para un diccionario. Pero en su caso, puede asumir que no hay colisión entre los hash de los caracteres. CPython3.8.5 en Ubuntu: >>> importar cadena [LF] >>> len(set(hash(c) para c en cadenag.printable)) == len(string.printable) [LF] Verdadero. Si conoce el conjunto de claves, siempre puede crear una función hash sin colisiones (consulte: en.wikipedia.org/wiki/Perfect_hash_function).
-jferard
29/03/2021 a las 9:03
------------------------------------
No creo que puedas ir más allá de lo lineal con este problema, ya que no es posible comprobar si una letra pertenece a la sopa de letras sin analizarla, y obviamente debes analizar tu mensaje.
PERO, su solución solo es lineal en PROMEDIO, ya que los mapas hash tienen una complejidad constante en promedio solo. Entoncesla complejidad del peor de los casos es más bien O(s^2+s.m).
Puede mejorarlo utilizando su propia estructura de datos que no se basa en hash sino en árboles binarios, por ejemplo, para lograr el peor de los casos con una complejidad de O(s.log(s)+ m.log(s)).
Editar: también puedes aprovechar el hecho de que tus caracteres son sólo ASCII.
def checkBowl(message, soup):
d = [0 for i in range(128)]
# O(S)
for c in soup:
d[ord(c)] +=1
# O(m)
for c in message:
if(d[ord(c)] == 0):
return False
else:
d[ord(c)] -= 1
# So the overall time complexity is O(m+s)
return True
10
Ah, claro. Olvidé por completo que la complejidad de la tabla hash en el peor de los casos es O (n). Gracias :)
Yo.
29 de marzo de2021 a las 6:14
Pero al usar heap, que es un árbol binario completo, el orden sería O(s.log(s)+m.log(m)), no O(s.log(s)+m.log(s) ). ¿Estoy en lo cierto? Quiero decir que cometiste un error tipográfico en la última línea de tu respuesta o no entendí bien la solución usando un árbol binario.
Yo.
29 de marzo de 2021 a las 7:28
@Yo. Estaba pensando en una solución donde la única diferencia con su solución actual es la implementación del mapa, usando un árbol sobre hash. ¿Qué eres tú?¿Tu idea de una solución?
Amante de TUI
29 de marzo de 2021 a las 7:33
@Yo. ¿Conoce la topología del alfabeto a partir del cual se genera la sopa de letras? Tengo una solución verdaderamente lineal si sabes qué personaje puedes encontrar
Amante de TUI
29 de marzo de 2021 a las 8:34
1
Lo hago lo antes posible
Amante de TUI
29 de marzo de 2021 a las 8:59
