Algoritmo para encontrar lenth de secuencia más larga de espacios en blanco en una cadena dada

Question

¿Busca un algoritmo para encontrar la longitud de la secuencia más larga de espacios en blanco en una cadena dada examinando la menor cantidad de caracteres posible?

Sugerencia: Su programa debe ser más rápido a medida que aumenta la longitud de la secuencia de espacios en blanco.

sé la solución, que es O (n) .. Pero en busca de solución más óptima

Answer 1

Pero en el peor de los casos (cuando todos los personajes están en blanco), tiene que examinar cada carácter. Entonces no puede ser mejor que O (n) en complejidad.

Justificación: supongamos que toda la cadena está en blanco, no ha examinado N caracteres y sus algoritmos producen n. Entonces, si algún personaje no examinado no está en blanco, su respuesta sería incorrecta. Entonces, para esta entrada particular, debes examinar toda la cadena.

Answer 2

No podrá encontrar una solución que sea de una complejidad menor que O (n) porque necesita pasar por todos los caracteres en el peor de los casos con una cadena de entrada que tenga como máximo 0 o 1 espacio en blanco consecutivo, o es completamente en blanco

Sin embargo, puede hacer algunas optimizaciones, pero seguirá considerándose O (n).

Por ejemplo:

Sea M el actual partido más largo hasta el momento a medida que avanza a través de su lista. Supongamos también que puede acceder a los elementos de entrada en O (1), por ejemplo, tiene una matriz como entrada.

Cuando ve un espacio no en blanco, puede omitir elementos M si el current + M no es un espacio en blanco. Seguramente, ningún espacio en blanco más largo que M puede estar contenido dentro.

Y cuando ve un caracter de picea blanca, si current + M-1 no es un espacio en blanco, sabe que no tiene las ejecuciones más largas o puede omitir también en ese caso.

Answer 3

Lo que sea que hagas, el peor caso siempre será o (n) - si esos espacios en blanco están en la última parte de la cadena ... (o la última parte "marcada" de la cadena).

Answer 4

La idea obvia: puede saltar por K + 1 lugares (donde K es la secuencia espacial más larga) y escanear hacia atrás si encuentra un espacio.

De esta manera tiene algo sobre (n + n/M)/2 = n (M + 1)/2M posiciones marcadas.

Editar:
Otra idea sería aplicar un tipo de búsqueda binaria. Esto es como sigue: para un k determinado se realiza un procedimiento que verifica si hay una secuencia de espacios con longitud> = k. Esto se puede lograr en O (n/k) pasos. A continuación, intente encontrar el máximo k con búsqueda binaria.

Editar:
Durante los registros consiguientes, se puede utilizar el conocimiento de que la secuencia de cierta longitud k ya existen, y empezar a saltar al k desde el principio.

Answer 5

No hay forma de hacerlo más rápido que O(N) en el peor de los casos. Sin embargo, aquí hay algunas optimizaciones, suponiendo indexación basada en 0.

1. Si ya tiene una secuencia completa de L espacios en blanco (por completo me refiero a una secuencia que no es una subsecuencia de una secuencia más grande), y L es al menos tan grande como la mitad del tamaño de su cadena, puede parar.
2. Si tiene una secuencia completa de espacios en blanco L, una vez que golpea un espacio en la posición i compruebe si el carácter en la posición i + L también es un espacio. Si es así, continúe escaneando desde la posición i hacia adelante ya que puede encontrar una secuencia más grande; sin embargo, si encuentra un espacio no ocupado hasta la posición i + L, puede saltarse directamente al i + L + 1. Si no es un espacio, no hay forma de que pueda construir una secuencia más grande comenzando en i, por lo que puede escanear hacia delante comenzando desde i + L + 1.
3. Si usted tiene una secuencia completa de piezas de partida de longitud L, y que están en la posición i y tiene k posiciones de izquierda a examinar, y k <= L, puede detener su búsqueda, ya que, obviamente, no hay forma en que será capaz de encuentra algo mejor nunca más

Para demostrar que no puede hacerlo más rápido que O(N), considere una cadena que no contiene espacios. Tendrás que acceder a cada carácter una vez, por lo que es O(N). Lo mismo con una cadena que no contiene más que espacios.