Analyse de la complexité temporelle du code
-
07-07-2019 - |
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?
La solution
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)
Autres conseils
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.
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.
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.
É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.
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)
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.