L'évolution des matériels informatiques, y compris la mémoire vive, a été significative au fil du temps. Autrefois mesurée en kilooctets, elle atteint aujourd'hui plusieurs gigaoctets, rendant l'occupation mémoire des algorithmes un facteur moins critique qu'auparavant. Cependant, la cmoplexité spatiale reste un concept pertinent pour évaluer l'utilisation de la mémoire par un algorithme.

Occupation Mémoire Courante en Java

Pour estimer l'empreinte mémoire, il est utile de connaître le fonctionnement de Java :

• Types de données primitifs : leur occupation mémoire est fixe :
  • byte : 1 octet
  • short : 2 octets
  • int : 4 octets
  • long : 8 octets
  • float : 4 octets
  • double : 8 octets
  • boolean : 1 octet
  • char : 2 octets
• L'accès à la mémoire se fait octet par octet.
• Une référence (adresse mémoire) requiert 8 octets.
• La création d'un objet (par exemple, new Date()) implique une surcharge : outre la mémoire pour les données internes de l'objet, 16 octets sont réservés pour les métadonnées de l'objet lui-même.
• Java tend à aligner l'utilisation de la mémoire sur des multiples de 8 octets. Si l'espace requis est inférieur à 8 octets, il est généralement complété pour atteindre 8 octets.
• Les tableaux en Java sont considérés comme des objets. Ils nécessitent une surcharge de 24 octets pour les métadonnées (16 octets de frais généraux d'objet + 4 octets pour la taille du tableau + 4 octets de remplissage), en plus de l'espace nécessaire pour stocker les éléments eux-mêmes.

Calcul de la Complexité Spatiale

La complexité spatiale d'un algorithme, notée S(n) = O(f(n)), décrit la quantité de mémoire supplémentaire nécessaire en fonction de la taille de l'entrée 'n'.

Exemple : Inverser un tableau d'entiers.

Solution 1 (modification sur place) :

public static int[] inverserSurPlace(int[] tableau) {
    int taille = tableau.length; // Allocation pour 'taille' (4 octets)
    int temporaire; // Allocation pour 'temporaire' (4 octets)
    for (int debut = 0, fin = taille - 1; debut < fin; debut++, fin--) {
        temporaire = tableau[debut];
        tableau[debut] = tableau[fin];
        tableau[fin] = temporaire;
    }
    return tableau;
}

Solution 2 (création d'un nouveau tableau) :

public static int[] inverserNouveauTableau(int[] tableau) {
    int taille = tableau.length; // Allocation pour 'taille' (4 octets)
    // Allocation pour 'tableauTemporaire' : (taille * 4 octets) + 24 octets pour les métadonnées du tableau
    int[] tableauTemporaire = new int[taille];
    for (int i = 0; i < taille; i++) {
        tableauTemporaire[i] = tableau[taille - 1 - i];
    }
    return tableauTemporaire;
}

En négligeant la mémoire utilisée par les structures de contrôle de boucle, l'analyse spatiale donne :

• Algorithme 1 : L'espace supplémentaire alloué est constant (4 octets pour taille + 4 octets pour temporaire), soit 8 octets. La complexité spatiale est donc O(1).
• Algorithme 2 : L'espace supplémentaire alloué est de 4 octets pour taille + (4 * n) octets pour le tableau temporaire + 24 octets pour les métadonnées du tableau. Total : 4n + 28 octets. La complexité spatiale est donc O(n).

Du point de vue de l'occupation mémoire, l'algorithme 1 est préférable à l'algorithme 2.

Il est important de noter que le ramasse-miettes de Java et les optimisations du JVM rendent une évaluation précise de l'occupation mémoire complexe. Néanmoins, ces estimations de base permettent de raisonner sur l'utilisation des ressoucres.

Dans la plupart des environneemnts de développement Java modernes, où la mémoire est abondante (plusieurs gigaoctets), la complexité spatiale est rarement le facteur limitant principal ; on se concentre généralement sur la complexité temporelle. Cependant, dans des contextes comme le développement embarqué sur des systèmes aux ressources très limitées (quelques kilo-octets de mémoire), la complexité spatiale devient une considération primordiale.