Python: problema de sopa de letras con la mejor complejidad temporal posible

CorePress2024-01-25  154

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

Su guía para un futuro mejor - libreflare
Su guía para un futuro mejor - libreflare