En général, décider de la complexité de l'algorithme est théoriquement impossible.
Cependant, une froide et centrée sur le code de la méthode pour le faire est de penser en termes de programmes directement. Prenez votre exemple:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
}
}
Maintenant, nous voulons analyser sa complexité, nous allons donc ajouter un simple compteur qui compte le nombre d'exécutions de l'intérieur de la ligne:
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("*");
counter++;
}
}
Parce que le Système.out.println ligne n'a pas vraiment d'importance, nous allons la supprimer:
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
counter++;
}
}
Maintenant que nous avons seulement le compteur de gauche, on peut évidemment simplifier l'intérieure de la boucle:
int counter = 0;
for (int i = 0; i < n; i++) {
counter += n;
}
... parce que nous savons que l'incrément est exécuté exactement n fois. Et maintenant, nous voyons que le compteur est incrémenté par n exactement n fois, afin de nous simplifier ainsi:
int counter = 0;
counter += n * n;
Et nous en sommes sortis avec le (bon) O(n2) complexité :) C'est là, dans le code :)
Voyons comment cela fonctionne pour récursive de Fibonacci de la calculatrice:
int fib(int n) {
if (n < 2) return 1;
return fib(n - 1) + fib(n - 2);
}
Modification de la routine de sorte qu'elle retourne le nombre d'itérations passé à l'intérieur à la place de la suite de Fibonacci:
int fib_count(int n) {
if (n < 2) return 1;
return fib_count(n - 1) + fib_count(n - 2);
}
C'est encore de Fibonacci! :) Donc, nous savons maintenant que le récursive de Fibonacci de la calculatrice est de complexité O(F(n)) où F est le nombre de Fibonacci lui-même.
Ok, regardons quelque chose de plus intéressant, de dire simple (et inefficace) mergesort:
void mergesort(Array a, int from, int to) {
if (from >= to - 1) return;
int m = (from + to) / 2;
/* Recursively sort halves */
mergesort(a, from, m);
mergesort(m, m, to);
/* Then merge */
Array b = new Array(to - from);
int i = from;
int j = m;
int ptr = 0;
while (i < m || j < to) {
if (i == m || a[j] < a[i]) {
b[ptr] = a[j++];
} else {
b[ptr] = a[i++];
}
ptr++;
}
for (i = from; i < to; i++)
a[i] = b[i - from];
}
Parce que nous ne sommes pas intéressés par le résultat, mais la complexité, nous changer de la routine de sorte qu'il retourne en fait le nombre d'unités de travail effectué:
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
/* Recursively sort halves */
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
/* Then merge */
Array b = new Array(to - from);
int i = from;
int j = m;
int ptr = 0;
while (i < m || j < to) {
if (i == m || a[j] < a[i]) {
b[ptr] = a[j++];
} else {
b[ptr] = a[i++];
}
ptr++;
count++;
}
for (i = from; i < to; i++) {
count++;
a[i] = b[i - from];
}
return count;
}
Puis nous supprimer ces lignes qui ne sont pas réellement l'impact des comtes et simplifier:
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
/* Recursively sort halves */
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
/* Then merge */
count += to - from;
/* Copy the array */
count += to - from;
return count;
}
Toujours en simplifiant un peu:
int mergesort(Array a, int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
int count = 0;
count += mergesort(a, from, m);
count += mergesort(m, m, to);
count += (to - from) * 2;
return count;
}
Nous pouvons maintenant passer de la matrice:
int mergesort(int from, int to) {
if (from >= to - 1) return 1;
int m = (from + to) / 2;
int count = 0;
count += mergesort(from, m);
count += mergesort(m, to);
count += (to - from) * 2;
return count;
}
Nous pouvons maintenant voir que en fait les valeurs absolues de partir et de ne pas faire plus d'importance, mais seulement de leur distance, de sorte que l'on modifie ainsi:
int mergesort(int d) {
if (d <= 1) return 1;
int count = 0;
count += mergesort(d / 2);
count += mergesort(d / 2);
count += d * 2;
return count;
}
Et puis, nous arrivons à:
int mergesort(int d) {
if (d <= 1) return 1;
return 2 * mergesort(d / 2) + d * 2;
}
Ici, évidemment, d sur le premier appel est la taille du tableau à trier, vous avez donc la récurrence de la complexité M(x) (c'est à la vue de tous sur la deuxième ligne :)
M(x) = 2(M(x/2) + x)
et ce que vous devrez résoudre pour arriver à une solution de la forme finie. Ce que vous faites le plus facile par deviner la solution de M(x) = x log x, et de vérifier pour le côté droit:
2 (x/2 log x/2 + x)
= x log x/2 + 2x
= x (log x - log 2 + 2)
= x (log x - C)
et vérifiez qu'il est asymptotiquement équivalent à la gauche:
x log x - Cx
------------ = 1 - [Cx / (x log x)] = 1 - [C / log x] --> 1 - 0 = 1.
x log x
