Discussion :

[frieden]

Bonjour à tous,

Je voudrais déterminer la complexité de cet algorithme ou disons de ces 2 méthodes qui servent ensemble à vérifier si un nombre est pair ou impair.

Quelle est sa complexité? Est-elle assez efficace ou tout à fait inefficace? Merci de vos réponses.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
	static boolean foo (int n) {
		int a=0, b=0; 
	    if (n==0) {
 
	        return false;
	    } else {
 
	        return bar(n-1);
	    }
	}
 
	static boolean bar (int n) {
	    if (n==0) {
	        return true;
	    } else {
	        return foo(n-1);
	    }
 
	}

S

[professeur shadoko]

foo(-1) doit donner une exécution intéressante

[frieden]

foo(-1) produit un ..Exception in thread "main" java.lang.StackOverflowError.
Pour quoi ce résultat alors tout à l'air correcte pour d'autres valeurs? Il y a t'il quelque chose à en dédure de la complexité de l'algorithme?

[Nico02]

Sur sa complexité non, par contre sur ton programme tu peux effectivement en déduire qu'il ne marche pas très bien.

Fais une petite trace vite fait de ton programme à la main et tu verras vite où est le problème.

Pour ce qui est de la complexité bah, essais aussi de faire une petite trace en partant de foo(1) puis de foo(2) puis foo(3) par exemple et tu devrais pouvoir trouver la réponse tout seul

Cdt.

[frieden]

Je l'ai essayé. J'y ai ajouté une variable globale ck pour disons "compter" le nombre d'opérations comme vous le pouvez le constater. Ce n'est pas assez propre mais ça produit en sortie une séquence du type "1234567" pour n=6 et "1234.....501" pour n=500.
Je pourrais conclure que la complexité est linéaire... mais les problèmes recursives peuvent faire allusion à la complexité factorielle. En effet, le code montre que n est décrémenté jusqu'à 0 pour chaque passage successif dans foo et dans bar si je ne me trompe bien sûr.
Je débute en complexité et je suis un peu confus face à ces 2 choix..

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static int ck=0;
	static boolean foo (int n) {
	    if (n==0) {
	    	ck++;
	    	System.out.print(ck);
	        return false;
	    } else {
	    	ck++;
	    	System.out.print(ck);
	        return bar(n-1);
	    }
	}
 
	static boolean bar (int n) {
	    if (n==0) {
	    	ck++;
	    	System.out.print(ck);
	        return true;
	    } else {
	    	ck++;
	    	System.out.print(ck);
	        return foo(n-1);
 
	    }
 
	}

[tchize_]

Dis toi que la récursivité et les boucles, c'est grosso modo la même chose. Ici, à chaque appel tu te rapproche de 1 de la réponse (pour les nombres positif). Tu auras donc, pour un nombre n, n appels, ce qui veux dire une complexité de o(n). Pour qu'il y aie une complexité plus élevée, il aurait fallu que chaque appel de foo() implique m appels de bar(). Autrement dit que dans foo ou bar il y aie une boucle ou n'importe quel facteur multiplicateur.

[frieden]

Merci Tchize, c'est plus que clair à présent !
Très bonne suite à vous et je vous souhaite un excellent mois de Juin!