Quelle est la complexité temporelle de ma fonction? [dupliquer]
cette question a déjà une réponse ici:
- comment trouver la complexité temporelle d'un algorithme 9 réponses
- Big O, comment calculez-vous/approximatif? 22 réponses
- Trouver le Grand O de la Série Harmonique 3 réponses
commencé à étudier sur la complexité, je suis aux prises avec celui-ci:
void what(int n) {
int i;
for (i = 1; i <= n; i++) {
int x = n;
while (x > 0)
x -= i;
}
}
le premier pour loop est clairement O(n)
. La première itération est O(n)
, la seconde est O(n/2)
.. et comme ce log(n)
fois je suppose?
Ce qui signifie O(n) * O(log(n)) = O(n * log(n)) complexity
. Ai-je obtenir ce droit?
Edit: (pas une copie) je sais ce que Big O est. J'ai demandé la bonne évaluation dans un cas précis.
4 réponses
La boucle externe fonctionne "151920920."
pour chaque itération, les boucles intérieures tournent n / i
fois.
le nombre total de passages est:
n + n/2 + n/3 + ... + n/n
Asymptotiquement (en ignorant l'arithmétique des nombres entiers arrondissement), ce qui simplifie l'
n * (1 + 1/2 + 1/3 + ... + 1/n)
cette série converge vaguement vers n * log(n)
.
D'où la complexité est O (N. log(N)) comme prévu.
la première boucle intérieure tourne n
times
La deuxième boucle interne tourne n/2
fois
La troisième boucle interne tourne n/3
fois
..
Le dernier court Une fois
Donc n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n)
.
c'est n multiplié par la somme de la série harmonique, qui n'a pas une belle représentation de forme fermée. Mais comme indiqué ici il est O(log(n))
. Donc dans l'ensemble l'algorithme est O(n log(n))
comme alternative, utilisez une substitution de variable y = n - x
suivie d'une notation Sigma pour analyser le nombre d'itérations de la boucle interne while
de votre algorithme.
ce qui précède surestime, pour chaque boucle interne while, le nombre d'itérations de 1
pour les cas où n-1
n'est pas un multiple de i
, c.-à-d. où (n-1) % i != 0
. Comme nous l' procéder, nous supposerons que (n-1)/i
est un entier pour toutes les valeurs de i
, surestimant ainsi le nombre total d'itérations dans la boucle interne while
, incluant subséquemment le signe moins ou égal à (i)
ci-dessous. Nous procédons à L'analyse de notation Sigma:
où nous , à (ii)
, avons approximé le n
: th harmonique numéro par l'intégrale associée. Par conséquent , votre algorithme fonctionne dans O(n·ln(n))
, asymptotiquement.
en laissant le comportement asymptotique et en étudiant la croissance réelle de l'algorithme, nous pouvons utiliser les données d'échantillon de nice De exacte (n,cnt)
(où cnt
est le nombre d'itérations intérieures) paires par @chux (se référer à sa réponse), et comparer avec le nombre estimé d'itérations ci-dessus, i.e., n(1+ln(n))-ln(n)
. Il est évident que l' estimation harmonise parfaitement avec le nombre réel, voir les placettes ci-dessous ou cet extrait pour les nombres réels .
finalement notez que si nous laissons n->∞
dans la somme sur 1/i
ci-dessus, la série résultante est la série harmonique infinie , qui est, curieusement assez divergente. La preuve pour ce dernier utilise le fait que, dans la somme infinie de termes non nuls est naturellement infini lui-même. En pratique, Cependant, pour un suffisamment grand mais non infini n , ln(n)
est une approximation appropriée de la somme, et cette divergence n'est pas pertinente pour notre analyse asymptotique ici.
tente ceci par des tests et des graphiques. Le tracé log2 vs log2 semble assez linéaire. Quelque chose entre plus que linéaire O(n) et moins que O(n*log(n)). "Tirer" votre propre conclusion.
[Modifier]
en utilisant les formules mathématiques dérivées, le O() calculé est une limite supérieure de O(N * log(n)). Qui utilise des "fractions d'itérations de boucle" qui augmentent le nombre d'une fraction et non 1. Par exemple: Lorsque n
est 6, le nombre d'itérations est 6 + 3 + 2 + 1.5 + 1.2 + 1 = 14.7 boucles plutôt que réelle 6 + 3 + 2 + 2 + 2 + 1 = 16. Cette différence est relativement moins significative puisque n
augmente, donc la croissance légèrement inférieure à O(N * log(n)). Donc, en n'ignorant pas le code utilise des maths entières, nous avons une question beaucoup plus difficile.
unsigned long long what(int n) {
unsigned long long cnt = 0;
int i;
for (i = 1; i <= n; i++) {
int x = n;
while (x > 0) {
x -= i;
cnt++;
}
}
return cnt;
}
void wtest(int n) {
unsigned long long cnt = what(n);
printf("%d %llu\n", n, cnt);
fflush(stdout);
}
void wtests(void) {
int i = INT_MAX/2 + 1;
while (i > 0) {
wtest(i);
i /= 2;
}
}
int main(void) {
wtests();
return 0;
}
sortie
1073741824 23567395117
536870912 11411566988
268435456 5519718329
134217728 2666826555
67108864 1286897093
33554432 620190504
16777216 298466265
8388608 143418602
4194304 68802063
2097152 32947406
1048576 15746897
524288 7510048
262144 3573331
131072 1695816
65536 802493
32768 378537
16384 177921
8192 83286
4096 38803
2048 17973
1024 8275
512 3782
256 1713
128 765
64 337
32 145
16 61
8 24
4 9
2 3
1 1