Quelle est la complexité temporelle de ma fonction? [dupliquer]

cette question a déjà une réponse ici:

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.

86
demandé sur chqrlie 2016-02-11 00:20:53

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.

103
répondu chqrlie 2017-07-16 19:14:33

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))

32
répondu Eugene Sh. 2017-05-23 11:55:02

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.

enter image description here

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:

enter image description here

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 .

enter image description here


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.


18
répondu dfri 2016-02-11 21:30:01

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.


enter image description here

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
11
répondu chux 2016-02-11 16:05:43