Como mencionas, el teorema de Akra-Bazzi muestra que la solución a la recurrencia es O ( n log n ) para todo p ∈ ( 0 , 1 ) . Sin embargo, esto no revela la naturaleza de la dependencia de p . Para determinar esto último, podemos usar un enfoque de árbol de recursión.T( n , p )O ( n logn )p ∈ ( 0 , 1 )pags
En la raíz del árbol de recursión está el intervalo . Sus dos hijos son los intervalos { 1 , ... , p n } y { p n + 1 , ... , n } , cuya longitud total es nuevamente n . Cada uno de estos nodos tiene dos hijos (suponiendo que n sea lo suficientemente grande), y así sucesivamente. Por simplicidad, ignoramos los errores de redondeo, es decir, suponemos que p n{ 1 , ... n }{ 1 , ... , p n }{ p n + 1 , ... , n }nortenortep nes un entero; esto es solo un tecnicismo, y no me preocuparía por eso. Paramos el proceso cuando un nodo tiene una longitud como máximo . La complejidad del algoritmo es proporcional a la longitud total de los intervalos en el árbol. Cuando p ≠ 1 / 2 , las hojas (nodos en la que detener el proceso) tienen diferente profundidad, y que hace que sea más difícil de determinar la complejidad global.1p ≠ 1 / 2
Podemos obtener un límite superior simple al observar que el árbol tiene como máximo niveles: cada nodo es al menos un factor de 1 - p más pequeño que su padre. Al igual que en el análisis para p = 1 / 2 , la longitud total de intervalos en cualquier nivel es como máximo n , y se obtiene un límite superior de O ( n log 1 - p ( 1 / n ) ) en el tiempo de ejecución. Desde log 1 -Iniciar sesión1 - p( 1 / n )1 - pp = 1 / 2norteO ( n log1 - p(1/n)) ylog(1-p ) - 1 =-log(1-p)=p±O( p 2 )parappequeño, podemos escribir esto comoO(nlogn / p).log1−p(1/n)=logn/log(1−p)−1log(1−p)−1=−log(1−p)=p±O(p2)pO(nlogn/p)
Aquí hay un cálculo más preciso. Considere el nivel . Supongamos que no detenemos el proceso al alcanzar un pequeño intervalo. Podemos generar un vértice aleatorio tomando t pasos, en cada uno de los cuales vamos a la izquierda (por ejemplo) con probabilidad p y a la derecha (por ejemplo) con probabilidad 1 - p . Cada vez que damos un paso hacia la izquierda, el registro de la longitud del intervalo disminuye en - log p , y cada vez que damos un paso hacia la derecha disminuye en - log ( 1 - p ) . Un vértice está en el árbol real del registro de la longitud disminuida como máximo en el registro nttp1−p−logp−log(1−p)logn. El peso total de los intervalos en el nivel del árbol es exactamente la probabilidad de que un vértice generado de acuerdo con este proceso corresponda a una disminución de, como máximo, log n . Es decir, si D es la distribución que es igual a - log p con probabilidad p y to - log ( 1 - p ) con probabilidad 1 - p , y X 1 , … , X t ∼ D son independientes, entonces el peso total del nivel t estlognortere−logpagspags−log( 1 - p )1 - pX1, ... ,Xt∼ Dt . Para t super-constante, la variable aleatoria X 1 + ⋯ + X t se distribuye más o menos normalmente con la media [ - p log p - ( 1 - p ) log ( 1 - p ) ] t y la varianza lineal en t , entonces para t satisfactorio [ - pPr [ X1+ ⋯ + Xt≤ logn ]tX1+ ⋯ + Xt[ - p logp - ( 1 - p ) log( 1 - p ) ] ttt , digamos, la probabilidad será muy cercana a 1 , mientras que para t satisface [ - p log p - ( 1 - p ) log ( 1 - p ) ] t ≥ 2 log n , digamos, estará muy cerca de cero. Definiendo[−plogp−(1−p)log(1−p)]t≤(logn)/21t[ - p logp - ( 1 - p ) log( 1 - p ) ] t ≥ 2 lognorte (conocida como la función de entropía binaria), concluimos que el tiempo de ejecución es Θ ( n log n / h ( p ) ) (uniforme en p , como n → ∞ ). Como p → 0 tenemos h ( p ) ≈ - p log ph ( p ) = - p logp - ( 1 - p ) log( 1 - p )Θ ( n logn / h ( p ) )pagsn → ∞p → 0h ( p ) ≈ - p logpags, por lo que nuestra estimación anterior no fue ajustada.
Otra forma de ver el mismo análisis es tener una secuencia infinita de variables aleatorias independientes como antes, y definir un tiempo de detención T como la primera vez t tal que X 1 + ⋯ + X t ≥ log n . El tiempo de ejecución es entonces proporcional a n E [ T ] . El teorema de renovación elemental establece que lim n → ∞ E [ T ] /X1,X2,…TtX1+⋯+Xt≥lognnE[T] , lo que implica que el tamaño total de los intervalos es igual a ( 1 + o ( 1 ) ) n log n / h ( p ) . Más exactamente, para cada constante p el tamaño total de los intervalos es ( 1 + α p ( n ) ) n log n / h ( plimn→∞E[T]/logn=1/E[D]=1/h(p)(1+o(1))nlogn/h(p)p , donde α p ( n ) = o ( n ) . La convergencia en el teorema de renovación elemental es exponencial en el parámetro de tiempo, log n en nuestro caso, por lo que debería ser polinomial en n , es decir, α p ( n ) = O ( n - C p ) . La convergencia también es probablemente uniforme para p ∈ ( δ , 1 - δ ) para cualquier δ > 0 .(1+αp(n))nlogn/h(p)αp(n)=o(n)lognnαp(n)=O(n−Cp)p∈(δ,1−δ)δ>0
Resumiendo, la longitud total de los intervalos en el árbol de recursión, que es proporcional al tiempo de ejecución, es de la siguiente forma para cada : T ( n , p ) = ( 1 + o ( 1 ) ) n log npdondelognyh(p)=-plogp-(1-p)log(1-p)son llevados a la misma base, y elO(1)es una función dependiendo depy tendiendo a0conn.
T(n,p)=(1+o(1))nlognh(p),
lognh(p)=−plogp−(1−p)log(1−p)o(1)p0n
Además, probablemente sea cierto que para cualquier y cualquier p ∈ ( δ , 1 - δ ) es cierto que la longitud total de los intervalos tiene la forma T ( n , p ) = ( 1 + O ( n - C δ ) ) n log nδ>0p∈(δ,1−δ)dondeCδ>0y la constante O grande oculta dependen solo deδ. En particular, debería ser el caso de que para todas las constantesp1,p2,
limn→∞T(n,p1)
T(n,p)=(1+O(n−Cδ))nlognh(p),
Cδ>0δp1,p2
y la convergencia es polinomialmente rápida.
limn→∞T(n,p1)T(n,p2)=h(p2)h(p1),