Voici une fonction en C qui implémente la suite définie par $U(0) = 0$, $U(1) = 1$, et $U(n) = 3U(n-1) - U(n-2)$ pour tout $n \geq 2$ :

#include <stdio.h>

// Fonction pour calculer le n-ième terme de la suite
int suite(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        int U_n_2 = 0; // U(0)
        int U_n_1 = 1; // U(1)
        int U_n;

        for (int i = 2; i <= n; i++) {
            U_n = 3 * U_n_1 - U_n_2;
            U_n_2 = U_n_1;
            U_n_1 = U_n;
        }

        return U_n;
    }
}

int main() {
    int n;
    printf("Entrez la valeur de n : ");
    scanf("%d", &n);

    if (n < 0) {
        printf("La valeur de n doit être un entier positif ou nul.\n");
    } else {
        int resultat = suite(n);
        printf("U(%d) = %d\n", n, resultat);
    }

    return 0;
}

Explication du code :

1. Fonction suite :

   • Cette fonction prend un entier n en entrée et retourne le n-ième terme de la suite.
   • Si n est 0, elle retourne 0.
   • Si n est 1, elle retourne 1.
   • Pour les valeurs de n supérieures ou égales à 2, elle utilise une boucle pour calculer les termes de la suite en utilisant la relation de récurrence $U(n) = 3U(n-1) - U(n-2)$.

2. Fonction main :

   • Elle demande à l'utilisateur d'entrer une valeur pour n.
   • Elle vérifie que n est un entier positif ou nul.
   • Elle appelle la fonction suite pour calculer le n-ième terme de la suite et affiche le résultat.

Vous pouvez compiler et exécuter ce programme pour voir les termes de la suite pour différentes valeurs de n.

Si on appelle la fonction suite pour des valeurs de plus en plus grandes, on peut observer plusieurs phénomènes intéressants :

1. Croissance rapide des valeurs :

   • La suite définie par $U(n) = 3U(n-1) - U(n-2)$ croît très rapidement. Les valeurs des termes augmentent exponentiellement, ce qui signifie que pour des valeurs de $n$ même modérément grandes, les termes de la suite deviennent très grands.

2. Dépassement de capacité :

   • En C, les types de données entiers (comme int) ont une plage de valeurs limitée. Par exemple, un int sur une machine 32 bits peut représenter des valeurs allant de -2,147,483,648 à 2,147,483,647. Pour des valeurs de $n$ suffisamment grandes, les termes de la suite peuvent dépasser cette plage, ce qui entraîne un dépassement de capacité (overflow). Cela peut conduire à des résultats incorrects ou à un comportement imprévisible du programme.

3. Temps de calcul :

   • Bien que la complexité temporelle de la fonction soit linéaire $O(n)$, le temps de calcul peut devenir significatif pour des valeurs très grandes de $n$ en raison de la croissance exponentielle des valeurs des termes.

Exemple de comportement pour des valeurs croissantes de $n$ :

Pour illustrer, voici quelques termes de la suite pour des valeurs croissantes de $n$ :

• $U(0) = 0$
• $U(1) = 1$
• $U(2) = 3$
• $U(3) = 8$
• $U(4) = 21$
• $U(5) = 55$
• $U(6) = 144$
• $U(7) = 377$
• $U(8) = 987$
• $U(9) = 2584$
• $U(10) = 6765$
• ...

On voit que les valeurs augmentent très rapidement. Pour des valeurs de $n$ au-delà de 30 ou 40, les termes de la suite peuvent dépasser la capacité d'un int en C.

Solutions possibles pour gérer des valeurs très grandes :

1. Utiliser des types de données plus grands :

   • Utiliser des types de données comme long long en C, qui peuvent représenter des valeurs plus grandes.

2. Utiliser des bibliothèques de calcul en précision arbitraire :

   • Utiliser des bibliothèques comme GMP (GNU Multiple Precision Arithmetic Library) pour gérer des entiers de taille arbitraire.

3. Vérifier les dépassements de capacité :

   • Ajouter des vérifications dans le code pour détecter les dépassements de capacité et gérer ces cas de manière appropriée.

Voici un exemple de modification de la fonction pour utiliser long long :

#include <stdio.h>

// Fonction pour calculer le n-ième terme de la suite
long long suite(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        long long U_n_2 = 0; // U(0)
        long long U_n_1 = 1; // U(1)
        long long U_n;

        for (int i = 2; i <= n; i++) {
            U_n = 3 * U_n_1 - U_n_2;
            U_n_2 = U_n_1;
            U_n_1 = U_n;
        }

        return U_n;
    }
}

int main() {
    int n;
    printf("Entrez la valeur de n : ");
    scanf("%d", &n);

    if (n < 0) {
        printf("La valeur de n doit être un entier positif ou nul.\n");
    } else {
        long long resultat = suite(n);
        printf("U(%d) = %lld\n", n, resultat);
    }

    return 0;
}

Cette version utilise long long pour gérer des valeurs plus grandes, mais elle peut encore rencontrer des limitations pour des valeurs très grandes de $n$.

La complexité temporelle d'un algorithme mesure comment le temps d'exécution de l'algorithme augmente en fonction de la taille de l'entrée. Dans le cas de la fonction suite, la taille de l'entrée est représentée par le paramètre n.

Analysons la fonction suite pour comprendre pourquoi sa complexité temporelle est linéaire :

long long suite(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        long long U_n_2 = 0; // U(0)
        long long U_n_1 = 1; // U(1)
        long long U_n;

        for (int i = 2; i <= n; i++) {
            U_n = 3 * U_n_1 - U_n_2;
            U_n_2 = U_n_1;
            U_n_1 = U_n;
        }

        return U_n;
    }
}

Analyse de la complexité temporelle :

1. Cas de base :

   • Si n est 0 ou 1, la fonction retourne immédiatement une valeur constante (0 ou 1). Ces cas de base ont une complexité temporelle constante $O(1)$.

2. Boucle for :

   • Pour les valeurs de n supérieures ou égales à 2, la fonction utilise une boucle for qui itère de 2 à n.
   • La boucle effectue n - 1 itérations (de i = 2 à i = n).
   • À chaque itération, les opérations suivantes sont effectuées :
     • Calcul de U_n en utilisant l'expression 3 * U_n_1 - U_n_2.
     • Mise à jour des variables U_n_2 et U_n_1.
   • Chacune de ces opérations a une complexité temporelle constante $O(1)$.

3. Complexité totale :

   • La boucle for effectue n - 1 itérations, et chaque itération a une complexité $O(1)$.
   • Par conséquent, la complexité totale de la boucle est $O(n - 1)$, ce qui est équivalent à $O(n)$ en notation asymptotique (car les constantes et les termes de plus bas ordre sont ignorés).

Conclusion :

La fonction suite a une complexité temporelle linéaire $O(n)$ parce que le temps d'exécution de la fonction augmente linéairement avec la valeur de n. En d'autres termes, si n double, le temps d'exécution double également (à une constante près). Cela est dû à la boucle for qui effectue un nombre d'itérations proportionnel à n, avec chaque itération ayant un coût constant.

Si on implémente une version récursive de la fonction suite en reprenant directement la définition $U(n) = 3U(n-1) - U(n-2)$, la complexité temporelle sera exponentielle. Voici pourquoi :

Version récursive de la fonction :

long long suite_recursive(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return 3 * suite_recursive(n - 1) - suite_recursive(n - 2);
    }
}

Analyse de la complexité temporelle :

1. Cas de base :

   • Si n est 0 ou 1, la fonction retourne immédiatement une valeur constante (0 ou 1). Ces cas de base ont une complexité temporelle constante $O(1)$.

2. Appels récursifs :

   • Pour les valeurs de n supérieures ou égales à 2, la fonction fait deux appels récursifs :
     • suite_recursive(n - 1)
     • suite_recursive(n - 2)
   • Chaque appel récursif entraîne à son tour deux nouveaux appels récursifs, et ainsi de suite.

3. Arbre des appels récursifs :

   • L'arbre des appels récursifs pour cette fonction est un arbre binaire complet, où chaque nœud a deux enfants (sauf les feuilles qui correspondent aux cas de base).
   • La hauteur de cet arbre est n, et le nombre total de nœuds dans un arbre binaire complet de hauteur n est $2^{n+1} - 1$.

4. Complexité totale :

   • Le nombre total d'appels récursifs (et donc le nombre total d'opérations) est exponentiel en fonction de n.
   • La complexité temporelle de cette version récursive est donc $O(2^n)$.

Conclusion :

La version récursive de la fonction suite a une complexité temporelle exponentielle $O(2^n)$ parce que chaque appel récursif entraîne deux nouveaux appels récursifs, ce qui conduit à un arbre d'appels de taille exponentielle. Cela signifie que le temps d'exécution de la fonction augmente très rapidement avec la valeur de n, rendant cette version inefficace pour des valeurs de n même modérément grandes.