La complejidad de tiempo en el peor de los casos de búsqueda de amplitud es O (| V | + | E |). El gráfico que tiene palabras en inglés como nodos, que son adyacentes si difieren exactamente en una letra, es bastante escaso, por lo que el número de nodos domina en este caso. En otras palabras, lleva tiempo lineal en el número de palabras en el diccionario. Sin embargo, sería posible usar una lista de palabras con muchas palabras bastante similares, por ejemplo, todas las cadenas binarias de 8 bits, en las que predomina el número de bordes, haciendo que el peor de los casos sea cuadrático en el número de palabras.
De hecho, el método de búsqueda proporcionado en el enlace es una búsqueda bidireccional de amplitud, que podemos decir que es lineal en el peor de los casos en el tamaño del componente más pequeño que se busca. La razón por la que hago esta distinción es que, si usamos un gráfico en palabras en inglés , generalmente se desconectará: hay muchas palabras que no se pueden alcanzar de otras palabras. Algunos son nodos aislados, y algunos son pequeñas islas de algunas palabras similares. Pero si buscamos desde ambos extremos a la vez, podemos detenernos tan pronto como la búsqueda de cualquiera de las palabras no tenga más nodos en la cola. Es decir, tan pronto como la isla de esa palabra haya sido completamente explorada.
Por lo tanto, podríamos, si supiéramos más sobre el gráfico, decir que el peor tiempo de ejecución es lineal en el número de palabras del segundo componente más grande o lineal en la mitad del número de palabras en el componente más grande, lo que sea mayor.
- Cómo verificar si la suma de los números de la primera mitad y la segunda mitad de una matriz es la misma
- Tiene dos números binarios de tamaño n cada uno, ¿cuántas operaciones se necesitan para sumarlos?
- ¿Cuál es la diferencia entre los cursos avanzados de algoritmos 6.046 y 6.854 en el MIT?
- Si U = {todos los enteros positivos menores o iguales a 30} y N = {todos los números impares menores o iguales a 19}, ¿qué es N 'y n (N')?
- ¿Dónde puedo conectarme en línea para estudiar estructuras de datos, como árboles de búsqueda binarios, montones, etc.?
Cuando resolví una versión más general de este problema (Word warm warm warp), este peor de los casos se logró con regularidad, ya que no utilicé la búsqueda bidireccional (ya que me facilitaba manejar las restricciones adicionales que me daba a mí mismo). Traté de conectar una palabra bien conectada a una palabra desconectada de igual o mayor longitud, terminé buscando el componente completo de palabras del tamaño apropiado. Me tomaría mucho más tiempo que las palabras que están a solo unos saltos de distancia. . (En el enlace anterior, compare cuánto tiempo se tarda en calcular la falta de una ruta de “syzygy” a “print” que en encontrar con éxito la ruta más corta de “cordero” a “print”. Luego vea cómo no toma tiempo en absoluto decir que no hay un camino de “syzygy” a “monstruo”. Verá las enormes diferencias de tiempo entre los mejores, los peores y los casos promedio para una búsqueda unidireccional. Sin embargo, el caso promedio en mi implementación es mucho más rápido que el caso promedio de r BFS, ya que utilicé una búsqueda A *).
