Una secuencia binaria de longitud es solo una secuencia ordenada para que cada sea o . Para generar todas esas secuencias binarias, se puede usar la estructura de árbol binario obvia de la siguiente manera: la raíz está "vacía", pero cada hijo izquierdo corresponde a la adición de a la cadena existente y cada hijo derecho a un . Ahora, cada secuencia binaria es simplemente una ruta de longitud comienza en la raíz y termina en una hoja.x 1 , … , x n x j 0 1 0 1 n + 1
Aquí está mi pregunta:
¿Podemos hacerlo mejor si solo queremos generar todas las cadenas binarias de longitud que tienen exactamente ceros unos?n n
Por "podemos hacerlo mejor", quiero decir que deberíamos tener una complejidad menor que el algoritmo tonto que primero construye todo el árbol de arriba y luego trata de encontrar esos caminos con el mismo número de bordes "izquierdo" y "derecho".
fuente
Respuestas:
Obviamente hay cadenas binarias de longitud . Para atravesar el binario, un algoritmo debe visitar cada nodo una vez, es decir, debe hacer pasos.4n 2n
Consideremos un algoritmo recursivo que atraviesa el árbol que describió, pero cuenta el número de unos y ceros en su camino, es decir, solo atravesará la parte buena del árbol.n n n 2n
Pero, ¿cuántas cadenas binarias con 0 y 1 hay? Elegimos 1 para nuestras cadenas de longitud y utilizamos la fórmula de Stirling en el paso 2:
EDITAR
Gracias a los comentarios de Peter Shor, también podemos analizar la cantidad de pasos necesarios para el segundo algoritmo, que cuenta los 1 y los 0. Cito su comentario desde abajo:
Usando la fórmula de Stirling nuevamente obtenemos como el tiempo de ejecución del nuevo algoritmo.
fuente
Tal vez estoy siendo pesado, pero la pregunta original pedía una forma de generar todas las secuencias binarias "equilibradas" de longitud 2n que fuera más eficiente que atravesar un árbol de todas las secuencias binarias de longitud 2n y generar solo aquellas que estaban equilibradas. Entonces, ¿por qué usar un árbol?
Aquí hay un pseudocódigo para un algoritmo recursivo que genera todas esas secuencias (la palabra clave "rendimiento" envía una secuencia a la salida):
Si no estoy entendiendo algo, por favor dígame, pero me parece que esta es la respuesta más eficiente al problema realmente planteado, que nunca especificó el uso de un árbol.
fuente