algorithm - maestro - master theorem
Cálculo de la relación de recurrencia T(n)=T(n/log n)+Θ(1) (3)
Gracias por la respuesta de @AbcAeffchen
Soy el dueño de la pregunta, usando el conocimiento del "método maestro" que aprendí ayer, la parte de la prueba "un poco más difícil" se puede hacer de la siguiente manera.
Comenzaré aquí:
T(n) = T(sqrt(n)) + O(log(sqrt(n)) / log(log(sqrt(n))))
⇔ T(n)=T(sqrt(n)) + O(log n / log log n)
Dejar
n = 2 k , S (k) = T (2 k )
entonces nosotros tenemos
T (2 k ) = T (2 k / 2 ) + O (log 2 k / log log 2 k ) ⇔ S (k) = S (k / 2) + O (k / log k)
con el método maestro
S (k) = a * S (k / b) + f (k), donde
a=1, b=2, f (k) = k / log k = Ω (k log 2 1 + ε ) = Ω (k log 2 1 + ε ) = Ω (k log 2 1 + ε ) = Ω ( k ε )
siempre que ε∈(0,1)
para que podamos aplicar el caso 3. Luego
S (k) = O (k / log k)
T (n) = S (k) = O (k / log k) = O (log n / log log n)
La pregunta proviene de Introduction to Algorithms 3rd Edition, P63, Problem 3-6, donde se presenta como funciones iteradas . Lo reescribo de la siguiente manera:
int T(int n){
for(int count = 0; n > 2 ; ++count)
{
n = n/log₂(n);
}
return count;
}
Luego da un límite lo más ajustado posible en T(n) .
Puedo convertirlo en O(log n) y Ω(log n / log log n) , pero ¿puede ser más ajustado?
PD: Usando Mathematica, aprendí que cuando n=1*10^3281039 , T(n)=500000
y al mismo tiempo, T(n)=1.072435*log n/ log log n
y el coeficiente disminuye con n de 1.22943 ( n = 2.07126*10^235 ) a 1.072435 ( n = 1*10^3281039 ).
Puede que esta información sea útil.
Las agallas del problema de verificar la estimación conjeturada es obtener una buena estimación de cómo tapar el valor
n / log(n)
en la función
n --> log(n) / log(log(n))
Teorema
log( n/log(n) ) / log(log( n/log(n) )) = log(n)/log(log(n)) - 1 + o(1)
(en caso de problemas de lectura de fuentes, eso es poco, oh, no grande, oh)
Prueba:
Para guardar en notación, escriba
A = n
B = log(n)
C = log(log(n))
El trabajo se basa en la aproximación de primer orden al logaritmo (natural): cuando 0 < y < x ,
log(x) - y/x < log(x - y) < log(x)
El valor que estamos tratando de estimar es
log(A/B) / log(log(A/B)) = (B - C) / log(B - C)
Aplicando los límites para el logaritmo de una diferencia da
(B-C) / log(B) < (B-C) / log(B-C) < (B-C) / (log(B) - C/B)
es decir,
(B-C) / C < (B-C) / log(B-C) < (B-C)B / (C (B-1))
Tanto la recursión que intentamos satisfacer como el límite inferior sugieren que deberíamos estimar esto con B/C - 1 . Sacar eso de ambos lados da
B/C - 1 < (B-C) / log(B-C) < B/C - 1 + (B-C)/(C(B-1))
y así concluimos
(B-C) / log(B-C) = B/C - 1 + o(1)
Si quita una idea de este análisis para usarla por su cuenta, deje que sea el punto de usar aproximaciones diferenciales (o incluso series de Taylor de orden superior) para reemplazar las funciones complicadas por otras más simples. por ejemplo, una vez que tienes la idea de usar
log(x-y) = log(x) + Θ(y/x) when y = o(x)
luego, todos los cálculos algebraicos que necesita para su problema simplemente siguen directamente.
Parece que el límite inferior es bastante bueno, así que traté de probar que el límite superior es O(log n / log log n) . Pero permítanme primero explicar los otros límites (solo para una mejor comprensión).
TL; DR
T(n) está en Θ(log n / log log n) .
T (n) está en O(log n)
Esto se puede ver modificando n := n/log₂n a n := n/2 .
Necesita pasos O(log₂ n) hasta que n ≤ 2 mantenga.
T (n) está en Ω(log n / log log n)
Esto se puede ver modificando n := n/log₂(n) a n := n/m , donde m es el valor inicial de log n .
Resolviendo la ecuación n / (log n) x < 2 para x nos lleva a
log n - x log log n < log 2 ⇔ log n - log 2 < x log log n ⇔ (log n - log 2) / log log n < x ⇒ x ∈ Ω(log n / log log n)
Mejorando el límite superior: O(log n) → O(log n / log log n)
Ahora intentemos mejorar el límite superior. En lugar de dividir n por una constante fija (es decir, 2 en la prueba anterior) dividimos n como largo por el valor inicial de log(n)/2 ya que el valor actual de log(n) es mayor. Para ser más claro, eche un vistazo al código modificado:
int T₂(int n){
n_old = n;
for(int count=0; n>2 ;++count)
{
n = n / (log₂(n_old)/2);
if(log₂(n)) <= log₂(n_old)/2)
{
n_old = n;
}
}
return count;
}
La complejidad de la función T₂ es claramente un límite superior para la función T , ya que log₂(n_old)/2 < log₂(n) mantiene durante todo el tiempo.
Ahora necesitamos saber cuántas veces dividimos por cada 1/2⋅log(n_old) :
n / (log(sqrt(n)))x ≤ sqrt(n) ⇔ n / sqrt(n) ≤ log(sqrt(n))x ⇔ log(sqrt(n)) ≤ x log(log(sqrt(n))) ⇔ log(sqrt(n)) / log(log(sqrt(n))) ≤ x
Entonces obtenemos la fórmula de recurrencia T₂(n) = T(sqrt(n)) + O(log(sqrt(n)) / log(log(sqrt(n)))) .
Ahora necesitamos saber con qué frecuencia se debe expandir esta fórmula hasta que n < 2 válido.
n2-x < 2 ⇔ 2-x⋅log n < log 2 ⇔ -x log 2 + log log n < log 2 ⇔ log log n < log 2 + x log 2 ⇔ log log n < (x + 1) log 2
Entonces, necesitamos expandir la fórmula sobre log log n veces.
Ahora se pone un poco más difícil. (También eche un vistazo a la respuesta de Mike_Dog )
T₂(n) = T(sqrt(n)) + log(sqrt(n)) / log(log(sqrt(n))) = Σk=1,...,log log n - 1 2-k⋅log(n) / log(2-k⋅log n)) = log(n) ⋅ Σk=1,...,log log n - 1 2-k / (-k + log log n)) (1) = log(n) ⋅ Σk=1,...,log log n - 1 2k - log log n / k = log(n) ⋅ Σk=1,...,log log n - 1 2k ⋅ 2- log log n / k = log(n) ⋅ Σk=1,...,log log n - 1 2k / (k ⋅ log n) = Σk=1,...,log log n - 1 2k / k
En la línea marcada con (1) reordené la suma.
Entonces, al final, "solo" tenemos que calcular Σ k=1,...,t 2 k / k para t = log log n - 1 . En este punto, Maple resuelve esto para
Σk=1,...,t 2k / k = -I⋅π - 2t⋅LerchPhi(2, 1, t) +2t/t
donde I la unidad imaginaria y LerchPhi es el trascendente Lerch . Como el resultado de la suma anterior es un número real para todos los casos relevantes, podemos simplemente ignorar todas las partes imaginarias. El Lerch transcendente LerchPhi(2,1,t) parece estar en O(-1/t) , pero no estoy 100% seguro al respecto. Quizás alguien pruebe esto.
Finalmente, esto da como resultado
T₂(n) = -2t⋅O(-1/t) + 2t/t = O(2t/t) = O(log n / log log n)
Todos juntos tenemos T(n) ∈ Ω(log n / log log n) y T(n) ∈ O(log n/ log log n) ,
por lo tanto, se cumple T(n) ∈ Θ(log n/ log log n) . Este resultado también es respaldado por sus datos de ejemplo.
Espero que esto sea comprensible y ayude un poco.