¡Es una pregunta interesante! Te voy a dar mi opinión sobre esto.
En primer lugar, echemos un vistazo a un código de Python de muestra:
importar numpy como np
- ¿Cuáles son algunos conceptos que debo saber antes de aprender programación dinámica?
- ¿Qué tipo de ordenación usa C ++ para hacer múltiples clasificaciones?
- Cómo escribir un algoritmo para un programa complicado que tiene muchos bucles, conmutadores y otros procesos dentro de una instrucción if
- ¿Qué son P, NP, NP-complete y NP-hard?
- ¿En qué tipos de gráfico DFS y BFS producirán el mismo árbol (misma fuente) independientemente de la secuencia de visitas de los vecinos?
# Distribución de Bernoulli:
# Lanzar una moneda sesgada una vez con la probabilidad de aterrizar es p
# Devuelve 1 si la moneda cae cara, 0 de lo contrario.
def bernoulli (p):
return np.random.binomial (1, p)
# Devuelve una cadena binaria aleatoria de longitud l
# cada cadena de longitud l entre cadenas de 2 ^ l es igualmente probable.
# Tiempo de ejecución: O (l)
def randbistr (l):
s = “”
mientras len (s) <l:
s + = str (bernoulli (.5))
devoluciones
# Genera aleatoriamente n cadenas binarias distintas, cada una tiene la longitud de d.
# n debe ser menor o al menos igual a 2 ^ d.
def main (d = 3, n = 5):
resultado = [randbistr (d)]
while len (resultado) <n:
s = randbistr (d)
si no está en el resultado:
resultado.append (s)
# Prueba resutl
para s en resultado:
huellas dactilares)
if __name__ == ‘__main__’:
principal()
El tiempo de ejecución de la función main () depende del número de ejecuciones del bucle while, a su vez depende de si la siguiente cadena generada aleatoriamente es o no el resultado.
Hay [matemáticas] 2 ^ d [/ matemáticas] diferentes cadenas binarias de longitud [matemáticas] d [/ matemáticas]. Llame a este conjunto [matemáticas] S. [/ Matemáticas]
Cada vez dentro del ciclo while generamos aleatoriamente una cadena s independiente del resultado de cadenas generadas previamente . Entonces, cada cadena en [math] S [/ math] es igualmente probable que se genere con la probabilidad de [math] p = \ dfrac {1} {2 ^ d} [/ math].
Salimos del ciclo while hasta que la longitud del resultado es n. Asumir que el resultado tiene longitud [matemática] k <n [/ matemática] por ahora, la pregunta es: ¿cuántas iteraciones se necesitarían para aumentar la longitud del resultado en [math] 1 [/ math]?
Sea [math] X_k [/ math] el número de iteraciones que se necesitarían para aumentar la longitud del resultado de [math] k [/ math] a [math] k + 1 [/ math]. [math] X_k [/ math] es una variable aleatoria y el número total de ejecuciones del ciclo while es [math] X = X_0 + X_1 + X_2 + \ cdots + X_ {n-1} [/ math]. Por linealidad del valor esperado, tenemos: [matemática] E [X] = E [X_0] + E [X_1] + E [X_2] + \ cdots + E [X_ {n-1}] [/ matemática].
Piénselo de esta manera, si lanzamos una moneda sesgada con la probabilidad de que la cabeza caiga es [matemática] p [/ matemática], entonces el número de lanzamientos que tomaría hasta que tengamos la primera cara (éxito) se distribuye geométricamente (Geométrico distribución – Wikipedia), y el número esperado de lanzamientos hasta el primer éxito es [matemáticas] 1 / p [/ matemáticas]. Volviendo a nuestro análisis, para que la longitud del resultado se incremente en [math] 1 [/ math], las siguientes cadenas generadas aleatoriamente no deben estar presentes en el resultado (¡éxito!). Sea [math] p_k [/ math] la probabilidad de que s no esté en el resultado (¡éxito!), Tenemos: [math] p_k = \ dfrac {2 ^ d – k} {2 ^ d} [/ math]. Entonces [math] X_k [/ math] se distribuye geométricamente con la probabilidad de éxito [math] p_k [/ math]. Por lo tanto, [matemáticas] E [X_k] = \ dfrac {1} {p_k} [/ matemáticas].
Combina todo lo anterior, tenemos:
[matemática] E [X] = \ dfrac {1} {p_0} + \ dfrac {1} {p_1} + \ cdots + \ dfrac {1} {p_ {n-1}} [/ matemática].
Si lo desea, puede simplificar esta ecuación para obtener un mejor resultado.
Tenga en cuenta que: para simplificar el análisis, no tengo en cuenta el tiempo que se tarda en generar una cadena binaria aleatoria y el tiempo que se tarda en comprobar si s está en resultado.
¡Espero que ayude!
