int foo(int n)
{
int x=2;
while (x<n)
{
x = x*x*x;
}
return x;
}
I need to analyze its time complexity. I noticed it reaches n much faster than just log(n). I mean, it does less steps than O(log(n)) would do. I read the answer but have no idea how they got to it: It is O(log(log(n)). Now, how do you approach such a question?
7 Réponses :
Si le code à l'intérieur de la boucle tandis que
x = 2*x;
Non, si le code était x = 2 * x, la complexité serait log (n). Avec quadrature de sa quête Nature O (journal (journal (n)) avec un facteur différent.
Pourquoi ne pas ajouter une variable de compteur pour compter le nombre d'itérations de la boucle. Imprimez-le juste avant que la fonction ne renvoie.
Appelez ensuite la fonction pour une gamme de valeurs, par exemple. 3 à 1 000 000 $ pour commencer. Tracez ensuite votre résultat en utilisant quelque chose comme gnuplot .
Voir si le graphique correspond à une courbe connue.
C'est une bonne idée, mais c'est une question d'un examen et je devrais savoir résoudre ce problème sans cet outil
pense à cela comme une fonction récursive: si vous l'étendez: La fonction augmente comme la puissance du puissance ... donc le temps (itérations) pour atteindre un certain nombre (c'est-à-dire que le calcul de l'inverse de la fonction) est le logarithme du logarithme. comme dans votre exemple afin d'atteindre une valeur de si la fonction serait: alors le motif serait: et dans ce cas, l'inverse de la fonction serait un seul logarithme de base 2. Mon calcul n'est pas très rigoureux, mais j'espère Vous aurez l'idée. 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): n , il prend log_3 (log_2 (n)) Itérations (arrondis tout en traitant avec des entiers pour surpasser).
C'est bien utile car je sais (sorte de) comment gérer l'expression de récursivité comme: t (n) = t (n-1) + c La question est s'il y a une méthode pour modifier toute fonction à la récursive?
Oui, une boucle peut être exprimée avec une récursivité, il suffit de faire une expression qui dépend des valeurs précédentes, mais n'est parfois pas nécessaire; Dans ce cas, cela aurait pu être encore plus facile de le sauter et de mettre directement la formule analytique.
donné donc p> Combien plus rapide ou plus lent (mesuré par nombre d'itérations de la boucle) sera cette fonction que votre fonction? p> et combien de fois plus rapide ou plus lent cette fonction sera supérieure à votre fonction? p> 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 ) );
}
Le premier serait plus lent que le mien (en fait, de mon conférencier) sur la seconde, je ne sais pas
Lorsque vous envisagez BIG-O, vous prenez des opérations comme une fois constante, vous devez donc vous demander si cela fera le même nombre d'itérations. À quel moment de la fonction originale ne remplira-t-il pas une itération que ces deux? Quelles valeurs de x, n> 0 seront x
La fonction d'origine s'arrête lorsque X> N, où X est cubie dans chaque itération. À propos de l'autre partie de votre réponse, je ne sais pas: / N'est pas x
Donc, si la condition est vraie chaque fois que la condition correspondante est vraie dans l'original, a-t-il le même nombre d'itérations ou non?
Pensez à la manière dont X change avec le nombre d'itérations à travers la boucle. Chaque fois, vous cubez-le. Ainsi, après i itérations, la valeur sera de 2 cubes, en cube à nouveau ... et ainsi de suite, je fois. Utilisons x (i) pour désigner cette expression. Disons x (0) = 2, x (1) = 2 3, etc. (j'utilise un fort> B pour signifier une augmentation de la puissance de la bth). Nous avons fini quand x (i)> = n. Combien de temps cela prend-il? Soyons pour i. P>
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)
c'est utile, semble être quelque chose que je peux comprendre, merci
laisser
alors la réponse correcte est Commencez avec considère maintenant pour x = 2
n = 4, itérations prises = 1
n = 16, itérations prises = 2
n = 256, itérations prises = 3
n = 65536, itérations prises = 4
Ainsi, la complexité de temps est venant 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 sur
Si vous regardez cette attention avec précaution, cela s'avère être Donc, je pense que la réponse correcte est Généraliser cela, si
La base du logarithme n'est pas pertinente comme log_a (x) = log_b (x) / log_b (a) et o (c · x) = O (x) pour < code> c = const
Oui, je me rends compte que maintenant. C'est un peu déroutant. Il donne une impression que log_4 (x) fonctionnerait deux fois plus vite que log_2 (x).
let le nombre total d'étapes est le plus gros le logarithme augmente strictement, donc i est le nombre d'étapes d'itération et x (i) la valeur de x après i i i pas. Nous avons i de sorte que x (i)