public static void Comp(int n)
{
int count=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
for(int k=1;k<n;k*=2)
{
count++;
}
}
}
System.out.println(count);
}
Est-ce que quelqu'un sait quelle est la complexité du temps?Quelle est la complexité temporelle de cet algorithme?
Et quel est le Big Oh()
S'il vous plaît peut u me l'expliquer, étape par étape?
Celui qui vous a donné ce problème est presque certainement chercher la réponse n^2 log(n), pour des raisons expliquées par d'autres.
Cependant, la question n'a pas vraiment de sens. Si n > 2^30, k débordera, rendant la boucle interne infinie.
Même si nous traitons ce problème comme étant tout à fait théorique, et supposons n, k et count ne sont pas des Java int s, mais un certain type entier théorique, la réponse n^2 log n suppose que les opérations ++ et *= ont la complexité constante de temps, peu importe combien de bits sont nécessaires pour représenter les entiers. Cette hypothèse n'est pas vraiment valide.
EDIT
Il a été signalé à moi dans les commentaires ci-dessous que, selon la manière dont fonctionne le matériel, il est raisonnable de supposer que ++, *=2 et < ont tous la complexité de temps constant , peu importe le nombre de bits requis.Ceci invalide le 3ème paragraphe de ma réponse, mais s'il-vous-plaît, ne votez pas sur ma réponse. Je ne peux pas la supprimer maintenant qu'elle a été acceptée!
C'est généralement l'hypothèse, ce qui n'est pas incorrect. La multiplication par 2 est juste une opération de décalage dans hardwhare et «++» est juste un compteur, qui est un cycle d'horloge constant. consultez http://teahlab.com/ en particulier les articles de comptoir/circuits. La question n'est donc pas aussi théorique que vous le pensez. Dans le matériel, les hypothèses sont correctes. –
acceptant cela comme la réponse montre à quel point le PO est perdu et confus. La question n'est pas aussi théorique que ce type suppose, et il mentionne simplement que les autres réponses sont correctes. Alors, comment est-ce la bonne réponse? Un peu de réflexion, mon ami. Un peu de réflexion. –
@KonsolLabapen pour l'opération de décalage (c'est-à-dire multiplier par 2), le registre à décalage d'accès parallèle fonctionnerait-il? http://teahlab.com/4-Bit_Parallel_Access_Shift_Register/ Je suis allé sur le site et j'ai recherché le mot "shift" et c'est ce qui s'est passé. –
La complexité temporelle est O(n^2 log n). Pourquoi? chaque boucle for est une fonction de n. Et vous devez multiplier par n pour chaque boucle; sauf la boucle interne qui se développe comme log n. Pourquoi? pour chaque itération, k est multiplié par 2. Pensez au tri de fusion ou aux arbres de recherche binaires.
détails
pour les deux premières boucles: sommation de 1 de 0 à n, ce qui est n + 1 et de sorte que les deux premières boucles donnent (n+1)*(n+1)= n^2+2n+1= O(n^2)
pour la boucle de K, on a k croissant comme 1,2,4,8,16,32, ... de sorte que 2^k = n. Prenez le journal des deux côtés et vous obtenez k=log n
Encore une fois, pas clair?
Donc, si nous fixons m=0 et a=2 alors nous obtenons -2^n/-1 pourquoi est-a = 2? parce que c'est la valeur pour laquelle la série donne 2,4,8,16, ... 2^k
Incorrect, la boucle la plus interne prend log (n), ce qui rend le produit final O (n^2 log (n)) – Lalaland
Il veut probablement que la plus étroite puisse être donnée, ce que celui-ci ne l'est pas. –
@Lalaland Ce n'est pas faux, ce n'est pas juste. –
En théorie, ceci est O(n^2 * log(n)).
Chacune des deux boucles extérieures est O(n) et l'intérieure est O(log(n)), parce log base 2 de n est le nombre de fois que vous devez diviser par n2 pour obtenir 1.
Aussi c'est une limite stricte, i.e. le code est également Θ(n^2 * log(n))
Quelle est votre estimation. –
Je pense que c'est N^2 * logN. –