J'ai boucleDéterminer la complexité temporelle de la boucle for?
sum = 0 ;
for (i = n ; i > 0; i = i/3)
for (j = 0 ; j < n^3 ; j++)
sum++ ;
Je dois comprendre la complexité de temps en grande notation thêta, mais le i/3 dans la première boucle me prêter à confusion.
En mathématiques normales, cette boucle ne se terminera jamais. O (inf). En mathématiques discrètes, c'est O (n^3).
La boucle extérieure ...
for (i = n ; i > 0; i = i/3)
La boucle fonctionne alors i est supérieur à 0. Si i est positif, je réduire d'un tiers volonté jamais APPORTER i en dessous de 0 devenant très légèrement plus petit et plus petit .
Si i est un nombre à virgule flottante IEEE, il finira par atteindre 0 après un grand nombre d'itérations en fonction de la taille de vos flotteurs. Si les nombres sont supposés être des entiers (ce que je pense que vous demandez avec la variable discrete-mathematics), la boucle externe est O (log (n)) car je suis coupé d'un tiers à chaque itération et atteindra rapidement 0.
La boucle interne, isolée, est assez facile à voir comme O (n^3).
for (my $j = 0; $j < $n**3 ; $j++) {
$sum++;
}
Une boucle O (n^3) boucle à l'intérieur d'un O (log (n)) est O (n^3 log (n)) qui ne soit pas une courbe de croissance significativement différent de O (n^3).
Je confesse que l'idée de «je» * pas * être un type entier ne m'est pas apparu. Mais vous avez tort sur la complexité de l'ensemble; c'est O (n^3 log (n)). – Beta
@Beta Je l'ai juste jeté comme étant effectivement constant par rapport à n^3. Vous avez probablement raison, ce n'est pas techniquement correct, mais je ne pense pas que cela change de façon significative la courbe de croissance. – Schwern
La boucle externe est O (log n). Est-ce suffisant pour travailler? – Beta
Je veux dire que l'interne est n^3 ce qui ferait O (nlog (n))? – user3769402
Je pense que vous seriez mieux servi sur https://cs.stackexchange.com/ – Schwern