Algorithme Avec O(N log n) temps et O (1) complexité de l'espace vs O (n) temps et O (n) complexité de l'espace

expérience:

• si vous ne pouvez absolument pas vous permettre l'espace, dirigez la route de l'espace O (1).
• lorsque l'accès aléatoire est inévitable, dirigez la route O(n) space. (il est généralement plus simple et a une constante de temps plus petite.)
• lorsque l'accès aléatoire est lent(par ex. seek times), dirigez la route de l'espace O (1). (Vous pouvez généralement trouver un moyen d'être cache cohérente.)
• sinon, l'accès au hasard est rapide.) l'espace de la route. (c'est habituellement plus simple avec une constante de temps plus petite.)

notez qu'habituellement l'accès aléatoire est "rapide" si le problème s'inscrit dans une mémoire qui est plus rapide que le stockage goulot. (par exemple si les disques sont le goulot d'étranglement, la mémoire principale est assez rapide pour l'accès aléatoire - - - si la mémoire principale est le goulot d'étranglement, le cache CPU est assez rapide pour l'accès aléatoire)

en utilisant votre exemple d'algorithme spécifique Paire De Tableaux Somme, la version de hachage O(n) time Avec O (n) space sera plus rapide. Voici un petit benchmark JavaScript avec lequel vous pouvez jouerhttp://jsfiddle.net/bbxb0bt4/1/

j'ai utilisé deux algorithmes de tri différents, quick sort et radix sort dans le benchmark. Le tri Radix dans cette instance (tableau d'entiers de 32 bits) est l'algorithme de tri idéal et même il peut à peine rivaliser avec le hachage simple passage version.

Si vous voulez un système généralisé de l'opinion, en ce qui concerne la programmation:

• utiliser le temps O(N) avec l'algorithme O(N) space est préférable parce que l'implémentation sera plus simple, ce qui signifie qu'il sera plus facile à maintenir et à déboguer.

function apsHash(arr, x) {
    var hash = new Set();
    for(var i = 0; i < arr.length; i++) {
        if(hash.has(x - arr[i])) {
            return [arr[i], x - arr[i]];
        }
        hash.add(arr[i]);
    }
    return [NaN, NaN];
}

function apsSortQS(arr, x) {
    arr = quickSortIP(arr);
    var l = 0;
    var r = arr.length - 1;
    while(l < r) {
        if(arr[l] + arr[r] === x) {
            return [arr[l], arr[r]];
        } else if(arr[l] + arr[r] < x) {
            l++;
        } else {
            r--;
        }
    }
    return [NaN, NaN];
}

pour comparer deux algorithmes, tout d'abord, il devrait être clair que pour ce que nous les comparons. Si notre priorité est l'espace, l'algorithme avec T(n)=O(n log n) et S(n)=O(1), c'est mieux. En général, la seconde avec T(n)=O(n) & S(n)=O (n) est meilleure car l'espace pourrait être compensé mais le temps ne pourrait pas.

ce n'est pas vrai que vous pouvez toujours remplacer un O(n lg n) en temps O(1) espace de l'algorithme, avec O(n) en temps O(n) de l'espace. Cela dépend vraiment du problème, et il existe de nombreux algorithmes différents avec des complexités différentes pour le temps et l'Espace, pas seulement linéaire ou linéarithmique (par exemple n log n).

notez que o (1) space signifie Parfois (comme dans votre exemple) que vous devez modifier le tableau d'entrée. Donc, cela signifie en fait que vous avez besoin de O (n) espace, mais vous pouvez en quelque sorte utiliser la le tableau d'entrée comme votre espace (vs le cas de vraiment en utilisant seulement l'espace constant). Modification du tableau d'entrée n'est pas toujours possible.

quant au choix entre les différents algorithmes avec des caractéristiques différentes de temps et d'espace, il dépend de vos priorités. Souvent, le temps est le plus important, donc si vous avez assez de mémoire, vous choisirez l'algorithme le plus rapide (rappelez-vous que cette mémoire n'est utilisée que temporairement pendant que l'algorithme est en cours d'exécution). Si vous n'avez pas vraiment le espace requis, puis vous choisiriez un algorithme plus lent qui nécessite moins d'espace.

ainsi, la règle générale de base est de choisir l'algorithme le plus rapide (pas seulement par la complexité asymptotique, mais le monde réel le plus rapide temps d'exécution pour votre charge de travail régulière) qu'il est possible de répondre à ses besoins d'espace.

on devrait garder trois choses à l'esprit lors de la sélection d'une approche d'algorithme.

1. temps pendant lequel l'application se déroulera en douceur dans le pire des cas.
2. disponibilité de L'espace en fonction du type d'environnement dans lequel le programme sera exécuté.
3. réutilisation des fonctions créées.

compte tenu de ces trois points, nous pouvons décider quelle approche conviendra à notre demande.

Si je serait d'avoir un peu d'espace et données raisonnables qui lui sont fournies, alors la condition 2 jouera un rôle de premier plan. Ici, nous pouvons vérifier la douceur avec O(nlogn) et essayer d'optimiser le code et donner de l'importance à la condition 3. (Par exemple, l'algorithme de tri utilisé dans la somme des paires de tableaux peut être réutilisé à un autre endroit dans mon code.)

si j'avais assez d'espace, alors improviser à l'heure serait une préoccupation majeure. Ici, au lieu de réutilisabilité, on se concentrerait sur la rédaction de programme efficace dans le temps.

en Supposant que votre hypothèse est vraie. Etant donné le fait que dans la vie réelle, les ressources illimitées n'existent pas et que lors de la mise en œuvre d'une solution vous feriez de votre mieux pour mettre en œuvre la solution la plus fiable (une solution qui ne casse pas parce que vous avez consommé toute votre mémoire autorisée), je serais sage et aller avec :

Algorithm with O(n log n) time and O(1) space complexity

même si vous avez une grande quantité de mémoire et que vous êtes sûr que vous n'épuiserez jamais votre mémoire en utilisant des solutions qui consomment une grande quantité de mémoire pourrait causer de nombreux problèmes (vitesse de lecture/écriture, données de sauvegarde en cas de panne) et je suppose que personne n'aime l'application qui utilise 2Go de mémoire au démarrage et continue de croître au fil du temps comme s'il y avait une fuite de mémoire.

je suppose que le mieux est d'écrire un essai,

algorithme réel, quantité de données (n),

et l'utilisation de la mémoire motif sera importante.

ici d'une simple tentative pour modèle;

random () les appels de fonction et mod opérations pour le temps de la complexité,

accès aléatoire à la mémoire (lecture / écriture) pour la complexité de l'espace.

#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <math.h>

int test_count = 10;

int* test (long time_cost, long mem_cost){
  // memory allocation cost is also included
  int* mem = malloc(sizeof(int) * mem_cost);
  long i;
  for (i = 0; i < time_cost; i++){
    //random memory access, read and write operations.
    *(mem + (random() % mem_cost)) = *(mem + (random() % mem_cost));
  }
  return mem;
}


int main(int argc, char** argv){
  if (argc != 2) {
    fprintf(stderr,"wrong argument count %d \nusage: complexity n", argc);
    return -1;
  }

  long n = atol(argv[1]);

  int *mem1, *mem2;
  clock_t start,stop;

  long long sum1 = 0;
  long long sum2 = 0;

  int i = 0;
  for (i; i < test_count; i++){
    start = clock();
    mem1 = test(n * log(n), 1);
    stop = clock();
    free(mem1);
    sum1 += (stop - start);

    start = clock();
    mem2 = test(n , n);
    stop = clock();
    free(mem2);
    sum2 += (stop - start);

  }

  fprintf(stdout, "%lld \t", sum1);
  fprintf(stdout, "%lld \n", sum2);

  return 0;
}

désactiver optimisations;

gcc -o complexity -O0 -lm complexity.c

test;

for ((i = 1000; i < 10000000; i *= 2)); do ./complexity $i; done | awk -e '{print  / }'

résultats que j'ai obtenu;

7.96269

7.86233

8.54565

8.93554

9.63891

10.2098

10.596

10.9249

10.8096

10.9078

8.08227

6.63285

5.63355

5.45705

jusqu' à un certain point O(n) est de faire mieux dans ma machine,

après un certain point, O (N*logn) s'améliore, (Je n'ai pas utilisé le swap).