Efficacité spatiale des algorithmes

Question

Il semble qu'aucun des manuels d'algorithmes ne mentionne autant l'efficacité de l'espace, donc je ne comprends pas vraiment quand je rencontre des questions demandant un algorithme qui ne nécessite que de la mémoire constante.

Quel serait un exemple de quelques exemples d'algorithmes utilisant de la mémoire constante et des algorithmes n'utilisant pas de mémoire constante?

Answer 1

Exemple très simple: compter un nombre de caractères dans une chaîne. Il peut être itérative:

int length(const char* str) 
{ 
    int count = 0; 
    while(*str != 0) { 
     str++; 
     count++ 
    } 
    return count; 
} 

ou récursive:

int length(const char* str) 
{ 
    if(*str == 0) { 
     return 0; 
    } 
    return 1 + length(str + 1); 
} 

La première variante utilise seulement quelques variables locales quelle que soit la longueur de la chaîne - c'est la complexité de l'espace est O(1). La seconde si elle est exécutée sans élimination de récursivité nécessite une trame de pile séparée pour stocker l'adresse de retour et les variables locales correspondant à chaque niveau de profondeur - sa complexité spatiale est O(n) où n est la longueur de la chaîne.

Answer 2

Si un algorithme:

a) récursif un certain nombre de niveaux de profondeur qui dépend de N ou

b) alloue une quantité de mémoire qui dépend de N

alors il est pas constant Mémoire. Sinon, c'est probablement le cas: formellement c'est constant-memory s'il y a une limite supérieure constante sur la quantité de mémoire utilisée par l'algorithme, quelle que soit la taille/valeur de l'entrée. La mémoire occupée par l'entrée n'est pas incluse, donc parfois pour être clair, vous parlez de la mémoire "supplémentaire" constante.

Alors, voici un algorithme mémoire constante pour trouver le maximum d'un tableau d'entiers en C:

int max(int *start, int *end) { 
    int result = INT_MIN; 
    while (start != end) { 
     if (*start > result) result = *start; 
     ++start; 
    } 
    return result; 
} 

est ici un algorithme de mémoire non constante, car il utilise l'espace de pile proportionnel au nombre d'éléments dans le tableau d'entrée. Cependant, il pourrait devenir constant-memory si le compilateur est en quelque sorte capable de l'optimiser en un équivalent non-récursif (avec lequel les compilateurs C ne s'embarrassent pas, sauf parfois avec une optimisation de queue, qui ne ferait pas l'affaire ici):

int max(int *start, int *end) { 
    if (start == end) return INT_MIN; 
    int tail = max(start+1, end); 
    return (*start > tail) ? *start : tail; 
} 

Voici un algorithme de tri-espace constant (en C++ cette fois-ci), qui est O (n) ou à peu près (peut-être O (N * N!)):

void sort(int *start, int *end) { 
    while (std::next_permutation(start,end)); 
} 

Voici un algorithme de tri d'espace O (N), qui est l'heure O (N^2):

void sort(int *start, int *end) { 
    std::vector<int> work; 
    for (int *current = start; current != end; ++current) { 
     work.insert(
      std::upper_bound(work.begin(), work.end(), *current), 
      *current 
     ); 
    } 
    std::copy(work.begin(), work.end(), start); 
} 

Answer 3

Prendre un algorithme de tri sur un tableau par exemple. Vous pouvez utiliser un nouveau tableau de la même longueur que le tableau d'origine dans lequel vous avez placé les éléments triés (Θ (n)). Ou vous triez le tableau in-place et utilisez simplement une variable temporaire supplémentaire pour permuter deux éléments (Θ (1)).