Analyse de la complexité temporelle du code

Question

int foo(int n) 
{
    int x=2;
    while (x<n)
    {
        x = x*x*x;
    }

    return x;
}

Je dois analyser sa complexité temporelle. J'ai remarqué qu'il atteignait n beaucoup plus rapidement que simplement log(n). Je veux dire, cela fait moins d’étapes que ce que O(log(n)) ferait. J'ai lu la réponse, mais je n'ai aucune idée de la façon dont ils y sont parvenus: c'est O(log(log(n)). Maintenant, comment abordez-vous une telle question?

Answer 1

Laisser

L3 = se connecter à la base 3 L2 = Connectez-vous à la base 2

La réponse correcte est alors O (L3 (L2 (n)) et NOT O (L2 (L2 (n)).

Commencez par x = x * 2 . x augmentera de manière exponentielle jusqu’à atteindre n, rendant ainsi la complexité temporelle O (L2 (n))

Considérons maintenant x = x * x . x augmente plus vite que ci-dessus. À chaque itération, la valeur de x saute au carré de sa valeur précédente. En faisant quelques calculs simples, voici ce que nous obtenons:

Pour x = 2 n = 4, itérations prises = 1 n = 16, itérations prises = 2 n = 256, itérations prises = 3 n = 65 536, itérations prises = 4

Ainsi, la complexité temporelle est O (L2 (L2 (n)) . Vous pouvez le vérifier en mettant des valeurs supérieures à celles de n.

J'en viens maintenant à votre problème, x = x * x * x . Cela augmentera encore plus vite que x = x * x. Voici le tableau:

Pour x = 2 n = 8, itérations prises = 1 n = 512, itérations prises = 2 n = (512 * 512 * 512), itérations prises = 3 et ainsi de suite

Si vous regardez cela attentivement, cela se révèle être O (L3 (L2 (n)) . L2 (n) vous procurera la puissance de deux, mais depuis que vous prenez un cube de x à chaque itération, vous devrez vous connecter à la base 3 pour connaître le nombre correct d'itérations prises.

Je pense donc que la bonne réponse est O (log-to-base-3 (log-to-base-2 (n))

En général, si x = x * x * x * x * .. (k fois) , la complexité temporelle est alors O (log-to-base-k (log -to-base-2 (n)

Answer 2

pense-le comme une fonction récursive:

f(i) = f(i-1)^3

si vous le développez:

f(i) = ((f(i-k)^3)^3)[...k times] = f(i-k)^(3^k) = f(0)^(3^i)

la fonction augmente avec la puissance du pouvoir ... de sorte que le temps (itérations) pour atteindre un certain nombre (c’est-à-dire calculer l’inverse de la fonction) est le logarithme du logarithme.

Comme dans votre exemple f(0) = 2, nous voulons savoir quand f(i) >= n étant n le paramètre d'entrée (et i le nombre d'itérations):

f(i) = 2^(3^i) >= n
           3^i >= log_2(n)
             i >= log_3(log_2(n))

Donc, pour atteindre une valeur de takes log_3(log_2(n)), il <=> itère (arrondissez au-dessus lorsque vous utilisez des entiers pour le dépasser).

si la fonction serait:

f(i) = 2*f(i-1) //e.g. x=2*x

alors le motif serait:

f(i) = 2*2*[...k times]*f(i-k) = f(i-k)*(2^k) = f(0)*(2^i)

Et dans ce cas, l'inverse de la fonction serait un seul logarithme en base 2.

Mes calculs ne sont pas très rigoureux, mais j'espère que vous aurez l'idée.

Answer 3

Réfléchissez à la manière dont x change avec le nombre d'itérations dans la boucle. Chaque fois, vous le cube. Ainsi, après i itérations, la valeur sera de 2 cubes, de nouveau cubes ... et ainsi de suite. Utilisons x (i) pour désigner cette expression. Supposons que x (0) = 2, x (1) = 2 3, etc. (j'utilise un b pour signifier un pouvoir élevé au bth).

Nous avons terminé lorsque x (i) > = n. Combien de temps cela prend-il? Résolvons pour i.

First, we take a log on both sides: ln(x(i))>=ln(n)

ln(x(i)) = ln(x(i-1))*3 = ln(x(i-2))*(3**2) = ... = ln(x(0))*(3**i)

(the above uses [this property][1]: ln(x**b)==ln(x)*b)

so, 3**i * 2 >=ln(n). Let's take another logarithm:

ln(3**i * 2) = ln(2) + ln(3)*i 

so ln(2) + ln(3)* i >= ln(ln(n))

Now we can solve for i: i >= ( ln(ln(n))-ln(2) ) / ln(3)

Nous pouvons ignorer les facteurs constants, et nous en sommes arrivés à la conclusion que nous allons suivre les étapes log (log (log)). C'est la complexité de votre algorithme.

Si tout va bien, briser toutes les étapes comme cela aide.

Answer 4

Si le code à l'intérieur de la boucle while était

x = 2*x;

x atteindrait n en itérations O (log (n)). Puisque vous effectuez un cubage x au lieu de simplement le multiplier par une constante, vous atteindrez n plus rapidement.

Answer 5

Étant donné

log ( A * x )     == log ( A ) + log ( x )
log ( x * x * x ) == 3 * log ( x )

Alors

log ( log ( x * x * x ) ) == log ( 3 * log ( x ) )
                          == log ( 3 ) + log ( log ( x ) )

À quel point cette fonction sera-t-elle plus rapide ou plus lente (mesurée par le nombre d'itérations de la boucle) que votre fonction?

int log_foo ( int n ) 
{
    double          log_x = log ( 2 );
    const double    log_n = log ( n );

    while ( log_x < log_n )
    {
        log_x = 3 * log_x;
    }

    return exp ( log_x );
}

Et à quel point cette fonction sera-t-elle plus rapide ou plus lente que votre fonction?

int log_log_foo ( int n ) 
{
    double          log_log_x = log ( log ( 2 ) );
    const double    log_log_n = log ( log ( n ) );
    const double    log_3     = log ( 3 );

    while ( log_log_x < log_log_n )
    {
        log_log_x += log_3;
    }

    return exp ( exp ( log_log_x ) );
}

Mais cette fonction n'incrémente log_log_x que d'une constante, il est donc facile de calculer le nombre d'itérations.

Answer 6

Soit i le nombre d'étapes d'itération et x(i) la valeur de x après x(i) < n les étapes. Nous avons

x(0) = 2
x(i) = x(i-1)³

Le nombre total d'étapes est le plus grand <=> afin que <=>.

Nous avons

log x(i) = log x(i-1)³
         = 3·log x(i-1)
         = 3·log x(i-2)³
         = 3²·log x(i-2)
         = 3^i·log x(0)
         = 3^i·log 2

⇒  log log x(i) = log (3^i·log 2)
                 = log 3^i + log log 2
                 = i·log 3 + log log 2

Le logarithme augmente strictement, donc

x(i) < n ⇔        log log x(i) < log log n
         ⇔ i·log 3 + log log 2 < log log n
         ⇔                   i < (log log n - log log 2) / log 3 ∈ O(log log n)

Answer 7

Pourquoi ne pas ajouter une variable de compteur pour compter le nombre d'itérations de la boucle. Imprimez-le juste avant le retour de la fonction.

Appelez ensuite la fonction pour une plage de valeurs, par exemple. 3 à 1 000 000 pour commencer. Ensuite, tracez votre résultat en utilisant quelque chose comme GNUPlot .

Vérifiez ensuite si le graphique correspond à une courbe connue.