Salut à tous,

En fait, j'ai trouvé deux façon de calculer la Combinaison de p éléments parmi n, et je me demande lequel est meilleur de point de vue complexité en temps et en espace et pourquoi. Voici les deux algorithmes:

**********1ère méthode***********
Comb_1(n,p: entier): réel
Si (p=n) Alors Comb_1← 1
Sinon Si (p=1) Alors Comb_1 ← n
Sinon Comb_1← (n/p)*Comb_1(n-1,p-1)
Fin Comb_1

**********2ème méthode***********
Comb_2(n,p: entier): réel
Si ((p=0) ou (p=n)) Alors Comb_2← 1
Sinon Comb_2←Comb_2(n-1,p)+Comb_2(n-1,p-1)
Fin Comb_2

Merci Bcp

Salut,
Vu que tes algos sont récursifs, ils vont être très lents, mieux vaut une solution itérative (avec 1 ou 2 tableaux).
En voilà un exemple (itératif, 1 tableau). Si tu veux avec 2 tableaux, dis moi.
C'est en Javascript car je voulais tester tout de suite si ça marchait, mais tu peux facilement convertir.

function combinaison(n, p) {
    t = new Array(n); //Tableau de n éléments
    t[0] = 1;
    for (var i = 1; i <= n; i++) {
        t[i] = 1;
        for (var j = i - 1; j >= 1; j--) //On part de le fin pour ne pas écraser les valeurs.
            t[j] = t[j] + t[j - 1]; //On fait les calculs nécessaires.
    }
    return t[p]; //On renvoie la valeur recherchée.
}

Sinon, si tu veux vraiment rester dans le récursif, je pense que ton premier algo est le meilleur, car c'est une récursivité simple tandis que dans le second, il y a deux appels récursifs (très lent).

Merc mcc, en fait, je veux garder la récursivité car il s'agit d'applications pour la récursivité, donc, si on veut une solution récursive après qu'on a vu la solution itérative, j'ai trouvé ces deux solutions et je veux savoir laquelle est meilleur, je pense que je vais présenter les deux pour les élèves, mais je dois savoir laquelle est meilleur pour pouvoir expliquer la différence.

D'accord,
donc comme j'ai l'ai dit, je pense que le premier est plus rapide car il ne contient qu'un seul appel récursif, contrairement au second qui en contient deux .
Pour approfondir la question, il y a un tuto sur la complexité en algorithmique sur le site.

justement, le 1er avec 1 seul appel récursif et 1 division, et le 2ème aves 2 appels récursifs <=> tu veux dire que l'appel récursif est plus lent qu'une division réelle?

Alors là j'avoue ne pas trop savoir, il faudrait tester en c par exemple l'implémentation des deux algos et mesurer le temps d'exécution...

ok, je vais voir,

Merci beaucoup mcc

Tout dépend du langage dans lequel est codé l'algorithme, et je ne vois pas en quoi l'appel a une fonction est plus long (techniquement) qu'une division, qui n'est pas une opération simple comme la soustraction, la multiplication ou l'addition.(sur des entiers, sur des flottants, c'est un peu plus chaud)
En revanche, on devrait se poser des questions de complexité avant tout.
Et il me semble que ton deuxième algo a la même complexité que la solution naïve récursive de la suite de fibonacci, c'est à dire exponentielle en à vue de nez p, ce qui est très mauvais en pratique, surtout pour calculer ce nombre.
La première me semble en revanche beaucoup plus rapide, p appels récursifs à la fonction, et ça, ça va vite. Par contre, tu devrais rajouter la condition suivante: si p plus grand que n, alors ça vaut 0, sa risque de simplifier énormément de cas possibles (genre 100000 parmi 500, ça vaut zéro, alors, que le programme va faire 100 000 tours, et ça peut devenir chiant...)

une autre simplification du temps de calcul pratique (pas algorithmique) consiste a dire que si p est plus grand que n/2, alors on remplace p par n-p (et tu gagnera n/2 appels récursifs, sympa non?)

La deuxième est beaucoup plus lent car des appels récursifs sont dupliqués (par exemple l'appel C(n-2,p-1) est effectué deux fois, une fois par chacun des premiers sous-appels, C(n-1,p-1) et C(n-1,p)). Il faut faire le calcul mais à vue de nez la complexité est exponentielle.

La première méthode est rapide, mais attention aux pertes de précision sur les (n/p). Si tu travailles sur des flottants à précision limitée ça peut poser problème, si c'est juste un algorithme abstrait pourquoi pas. Il est linéaire en temps.

Citation : mcc

Vu que tes algos sont récursifs, ils vont être très lents, mieux vaut une solution itérative (avec 1 ou 2 tableaux).

Non, ce n'est pas vrai. Les compilateurs qui savent le faire optimisent très bien la récursion est elle peut être tout aussi rapide qu'une fonction itérative. Dans son cas, l'algorithme est linéaire en mémoire, mais on pourrait obtenir facilement une version proche en mémoire constante. Dans tous les cas, c'est mieux (si on fait attention aux problèmes posés par la division) que ta version itérative quadratique en temps et linéaire en mémoire.

Dans tous les deux algo tu as oublié des cas. Pour que ça soit plus rapide, augmente les conditions élémentaires
ex:si p=0;
et pense à renvoyer un code d'erreur si p>n
ça évitera au processeur de faire des calculs inutiles. Plus il y a de cas élémentaires mieux c'est

-
Edité par greatpapi 16 mars 2017 à 22:40:39

Merci pour tous ceux qui ont répondu à ma question, toutes les réponses m'ont énormément aidé.

marque resolu stp

svp comment calculer  combinaison(n,p); à l'aide de deux tableaux?

Merci d'avance!!

de la même manière avec laquelle tu calculerais C(n,p) à l'aide d'une matrice avec le triangle de pascal, c'est plus ou moins pareil

int C (int n, int p) {
  if (p > n || p < 0)
    return -1 ; //erreur
  for (i = 0 ; i < n ; i++) {
    m[i][0] = 1 ;
    m[i][i] = 1 ;
    for (j = 1 ; j < i ; j++) {
      m[i][j] = m[i-1][j] + m[i-1][j-1] ;
      if (j == p && i == n)
        return m[i][j] ;
    }
  }
}

En terme de complexité ça prend O(n*p) en plus détaille ça fait (exp (k)) avec k la taille de tes données d'entrée, donc k = log (n*p) 

de quelle type de rtecursiviter sagit'il?

@LibawoDieudonne Bonjour, merci de ne pas déterrer d'ancien sujet résolu.

Déterrage

Citation des règles générales du forum :

Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.

Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre.
En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.

Au lieu de déterrer un sujet il est préférable :

• soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
• soit de créer un nouveau sujet décrivant votre propre contexte
• ne pas répondre à un déterrage et le signaler à la modération

Je ferme ce sujet. En cas de désaccord, me contacter par MP.