Calcul de la relation de récurrence T (n)=T (n / log n) + Θ (1)

La question vient de Introduction aux Algorithmes 3ème Édition, P63, Problème 3-6, où il est présenté comme fonctions Itérées. Je réécrire sous la forme suivante:

int T(int n){
   for(int count = 0; n > 2 ; ++count)
   {
      n = n/log₂(n); 
   }
   return count;
}

puis donnez une limite aussi serrée que possible sur T(n).

je peux le faire O(log n) et Ω(log n / log log n), mais peut-il être plus serré?


PS: en utilisant Mathematica, j'ai appris que lorsque n=1*10^3281039,T(n)=500000

et dans le même temps, T(n)=1.072435*log n/ log log n

et le coefficient diminue avec n1.22943 (n = 2.07126*10^235)1.072435 (n = 1*10^3281039).

cette information Peut être utile.

15
demandé sur AbcAeffchen 2015-06-14 07:50:04

3 réponses

Il ressemble à la limite inférieure est assez bonne, j'ai donc essayé de prouver que la limite supérieure est O(log n / log log n). Mais permettez-moi d'abord d'expliquer les autres limites (juste pour une meilleure compréhension).

TL;DR

T(n)Θ(log n / log log n).

T(n) est dans O(log n)

ceci peut être vu en modifiant n := n/log₂nn := n/2.

Il a besoin d' O(log₂ n) les étapes jusqu'à ce que n ≤ 2 contient.

T (n) est en Ω(log n / log log n)

ceci peut être vu en modifiant n := n/log₂(n)n := n/m, où m est la valeur initiale de log n.

La résolution de l'équation n / (log n)x < 2x nous conduit à

               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)

Amélioration de la limite supérieure: O(log n) → O(log n / log log n)

essayons maintenant d'améliorer la limite supérieure. Au lieu de diviser n par une constante fixe (à savoir 2 au-dessus de la preuve), nous divisons n tant par la valeur initiale de log(n)/2 comme la valeur actuelle de log(n) est plus grand. Pour être plus claire regarder le code modifié:

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 complexité de la fonction T₂ est clairement une limite supérieure pour la fonction T, car log₂(n_old)/2 < log₂(n) tient tout le temps.

Maintenant, nous avons besoin de savoir combien de fois on divise par chaque 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 

nous obtenons donc la formule de récurrence T₂(n) = T(sqrt(n)) + O(log(sqrt(n)) / log(log(sqrt(n)))).

nous devons maintenant savoir combien de fois cette formule doit être étendue jusqu'à ce que n < 2 contient.

        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

nous devons donc étendre la formule à log log n fois.

maintenant c'est un peu plus difficile. (Voyez aussi le réponse 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

dans la ligne marquée avec (1) j'ai réorganisé la somme.

ainsi, à la fin nous" seulement " devons calculer Σk=1,...,t 2k / kt = log log n - 1. À ce point Maple résout cela à

Σk=1,...,t 2k / k = -I⋅π - 2t⋅LerchPhi(2, 1, t)  +2t/t

I est l'unité imaginaire et LerchPhi est le Fonction transcendante. Puisque le résultat pour la somme ci-dessus est un nombre réel pour tous les cas pertinents, nous pouvons juste ignorer toutes les parties imaginaires. La Fonction transcendante LerchPhi(2,1,t) semble O(-1/t), mais je n'en suis pas sûr à 100%. Peut-être que quelqu'un va le prouver.

Enfin, il en résulte

T₂(n) = -2t⋅O(-1/t) + 2t/t = O(2t/t) = O(log n / log log n)

Tous ensemble, nous avons T(n) ∈ Ω(log n / log log n) et T(n) ∈ O(log n/ log log n),

donc T(n) ∈ Θ(log n/ log log n) contient. Ce résultat est également supporté par votre exemple données.

j'espère que c'est compréhensible et ça aide un peu.

3
répondu AbcAeffchen 2017-05-23 12:02:36

l'essence du problème de vérifier l'estimation conjecturée est d'obtenir une bonne estimation de colmater la valeur

n / log(n)

dans la fonction

n --> log(n) / log(log(n))

Théorème:

log( n/log(n) ) / log(log( n/log(n) )) = log(n)/log(log(n)) - 1 + o(1)

(dans le cas de la police de lisibilité des questions, c'est peu-oh, pas grand-oh)

la Preuve:

Pour enregistrer sur la notation, écrire

A = n
B = log(n)
C = log(log(n))

le travail est basé sur l'approximation de premier ordre logarithme (naturel): quand 0 < y < x,

log(x) - y/x < log(x - y) < log(x)

La valeur que nous essayons d'estimation est

log(A/B) / log(log(A/B)) = (B - C) / log(B - C)

L'application des limites du logarithme d'une différence donne

(B-C) / log(B) < (B-C) / log(B-C) < (B-C) / (log(B) - C/B)

qui est

(B-C) / C < (B-C) / log(B-C) < (B-C)B / (C (B-1))

la récursion que nous essayons de satisfaire et la limite inférieure suggèrent que nous devrions estimer cela avec B/C - 1. Tirant que des deux côtés donne

B/C - 1 < (B-C) / log(B-C) < B/C - 1 + (B-C)/(C(B-1))

et donc nous concluons

(B-C) / log(B-C) = B/C - 1 + o(1)

si vous retirez une idée de cette analyse à utiliser sur votre propre, laissez-la Être le point d'utiliser des approximations différentielles (ou même série Taylor d'ordre plus élevé) pour remplacer les fonctions compliquées par des fonctions plus simples. par exemple, une fois que vous avez l'idée d'utiliser

log(x-y) = log(x) + Θ(y/x) when y = o(x)

alors tous les calculs algébriques que vous avez besoin pour votre problème simplement suivre directement.

1
répondu Hurkyl 2015-06-16 00:20:26

Merci pour la réponse de @AbcAeffchen

je suis le propriétaire de la question, en utilisant la connaissance de "la méthode du maître" j'ai appris hier, la partie "un peu plus difficile" de la preuve peut être fait comme suit simplement. The master method

je vais commencer ici:

T(n) = T(sqrt(n)) + O(log(sqrt(n)) / log(log(sqrt(n))))
⇔ T(n)=T(sqrt(n)) + O(log n  / log log n)

Let

n = 2 k, S (k)=T(2 k)

ensuite, nous avons

T (2 k) =T (2 k / 2) + O (log 2 k / journal le journal de 2 k) փ s (k) =S(k/2) + O( K/log k)

avec la méthode master

S (k)=A*S(k/b)+f(k), où a=1, b=2, f (k)=k / log k = Ω (kjournal 21 + ε) = Ω (k ε) փ

tant que ε∈(0,1)

donc nous pouvons appliquer le cas 3. Puis

S (k) = O(K/log k)

T (n) = S (k) = O(k/log k) = O(log n/ log n)

1
répondu Mike_Dog 2015-06-16 12:17:42