Quelle est la complexité temporelle de ma fonction?

Question

Commencé à étudier la complexité, j'ai du mal avec celui-ci:

 void what(int n) {
    int i;
    for (i = 1; i <= n; i++) {
        int x = n;
        while (x > 0)
            x -= i;
    }
}
 

Eh bien, la première boucle est clairement O(n) . La première itération est O(n) , la seconde est O(n/2) .. et comme ça log(n) fois je suppose? Ce qui signifie O(n) * O(log(n)) = O(n * log(n)) complexity . Ai-je bien compris?

Edit: (pas une copie) Je sais ce que Big O est. J'ai demandé l'évaluation correcte dans un cas particulier.

Answer 1

La boucle externe s'exécute n fois.

Pour chaque itération, les boucles internes sont exécutées n / i fois.

Le nombre total de pistes est

 n + n/2 + n/3 + ... + n/n
 

Asymptotiquement (en ignorant les arrondis arithmétiques entiers), cela simplifie comme

 n (1 + 1/2 + 1/3 + ... + 1/n)
 

Cette série converge vaguement vers n * log(n) .

Par conséquent, la complexité est O(N.log(N)) comme prévu.

Answer 2

La première boucle s'exécute n fois
La seconde boucle s'exécute n/2 fois
La troisième boucle s'exécute n/3 fois
.. Le dernier s'exécute 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'ont pas une belle forme fermée de la représentation. Mais comme le montre ici, c'est - O(log(n)). L'ensemble de sorte que l'algorithme est - O(n log(n))

Answer 3

Comme une alternative, utiliser une variable de substitution y = n - x suivie par la notation Sigma pour analyser le nombre d'itérations de l'intérieur de la while boucle de votre algorithme.

Le ci-dessus surestime, pour chaque intérieur lors de la boucle, le nombre d'itérations par 1 pour les cas où l' n-1 n'est pas un multiple de i, (n-1) % i != 0. Alors que nous avançons, nous allons supposer que (n-1)/i est un entier pour toutes les valeurs de i, d'où une surestimation du nombre total d'itérations dans le centre - while boucle, par la suite, y compris les moins ou signe égal au (i) ci-dessous. Nous avons procéder à la notation Sigma analyse:

où nous, en (ii), se sont chiffrées à l' n:th harmonique nombre par les associés intégrale. Par conséquent, vous algorithme s'exécute en O(n·ln(n)), asymptotiquement.

---

Laissant comportement asymptotique et l'étude de la croissance réelle de l'algorithme, nous pouvons utiliser la nice des données de l'échantillon de l'exacte (n,cnt) (où cnt nombre d'intérieure itérations) paires par @chux (voir sa réponse), et de les comparer avec l'estimation du nombre d'itérations à partir de ci-dessus, c'est à dire, n(1+ln(n))-ln(n). Il est évident que l'estimation harmoniser parfaitement avec le nombre réel, voir les parcelles ci-dessous ou cet extrait de code pour les nombres réels.

---

Notez enfin que si nous laissons n->∞ dans la somme sur 1/i - dessus, la série qui en résulte est l' infini de la série harmonique, qui est, curieusement, divergents. La preuve de ce dernier utilise le fait que, dans la somme infinie de termes non nuls est naturellement infini lui-même. Dans la pratique, cependant, pour une suffisamment grande, mais pas à l'infini n, ln(n) est une bonne approximation de la somme, et cette divergence n'est pas pertinent pour notre analyse asymptotique ici.

---

Answer 4

Essayez cette par des essais et des graphiques. La log2 vs log2 intrigue semble assez linéaire. Quelque chose de plus que linéaire O(n) et moins de O(n*log(n)). "Dessiner" votre propre conclusion.

[Modifier]

À l'aide de la mathématique dérivés des formules, les 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 par une fraction, et non pas 1. E. g. Lors de l' n 6, 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 importantes qu' n augmente, ce qui est légèrement inférieur à O(n * log(n)) de la croissance. Donc par ne pas l'ignorer code utilise math entier, nous avons un beaucoup plus difficile question.

---

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