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

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

où 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.