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

je suis curieux de savoir quel algorithme est le meilleur :

  • algorithme avec O(N log n) temps et O (1) complexité de l'espace
  • algorithme avec O(n) temps et O (n) complexité de l'espace

la plupart des algorithmes qui sont résolus dans O(N long n) Le temps et l'espace constant peuvent être résolus dans O(n) le temps en payant la pénalité en termes d'espace. L'algorithme est le meilleur ? Comment puis-je décider entre ces deux paramètres ?

Exemple: La Somme Des Paires De Tableaux

  1. peut être résolu en temps O (N logn) par Tri
  2. peut être résolu en utilisant des cartes de hachage dans le temps O(n) mais avec l'espace O(n)
13
demandé sur k_g 2015-03-23 02:10:03

8 réponses

sans réellement tester quoi que ce soit (un geste risqué!), Je vais prétendre que le O(n log n) en temps O(1)-espace de l'algorithme est probablement plus rapide que le O(n) en temps O(n) en espace de l'algorithme, mais il est encore probablement pas l'algorithme optimal.

tout d'abord, parlons-en d'un point de vue de haut niveau qui ignore les détails particuliers des algorithmes que vous décrivez. Un détail à garder à l'esprit est que bien que O(n)-temps algorithmes sont asymptotiquement plus rapide que O(n log n) - Temps les algorithmes ne sont plus rapides que par un facteur logarithmique. En gardant à l'esprit que le nombre d'atomes dans l'univers est d'environ 1080 (merci, la physique!), la base-2 log du nombre d'atomes dans l'univers est d'environ 240. D'un point de vue pratique, cela signifie que vous pouvez penser à ce facteur supplémentaire O(log n) Comme juste une constante. Par conséquent, pour déterminer si un O(n log n) algorithme sera plus rapide ou plus lent qu'un algorithme O(n) sur une entrée particulière, vous devez en savoir plus sur les constantes qui sont cachées par la notation big-O. Un algorithme qui s'exécute en temps 600n sera plus lent qu'un algorithme qui s'exécute en temps 2n log n pour tout n qui s'inscrit dans l'univers, par exemple. Par conséquent, en termes de performance wall-clock, pour évaluer quel algorithme est plus rapide, vous auriez probablement besoin de faire un peu de profilage sur l'algorithme pour voir lequel est plus rapide.

puis il y a les effets de la mise en cache et de la localité de référence. Mémoire d'ordinateur a un nombre énorme de des caches qui sont optimisés pour le cas où les lectures et les Écritures sont situées l'une à côté de l'autre. Le coût d'une mise en cache peut être énorme - des centaines ou des milliers de fois plus lent qu'un hit - donc vous voulez essayer de minimiser cela. Si un algorithme utilise la mémoire O(n), puis que n devient plus grand, vous devez commencer à vous inquiéter de la façon dont étroitement emballé vos accès de mémoire sera. S'ils sont étalés, alors le coût des erreurs de cache pourrait commencer à s'additionner assez rapidement, entraînant de manière significative la coefficient caché dans la notation big-O de la complexité temporelle. S'ils sont plus séquentiel, alors vous n'avez probablement pas besoin de trop s'inquiéter à ce sujet.

vous devez également faire attention à la mémoire totale disponible. Si vous avez 8 Go de RAM sur votre système et obtenir un tableau avec un milliard entiers de 32 bits, alors si vous avez besoin D'O (n) espace auxiliaire avec même une constante raisonnable, vous n'allez pas être en mesure d'ajuster votre mémoire auxiliaire dans la mémoire principale et il va commencer à se faire biper par le système D'exploitation, ce qui tue vraiment votre course.

enfin, il y a la question du hasard. Algorithmes basés sur le hachage attendu exécution rapide, mais si vous avez une mauvaise fonction de hachage, il y a une chance que l'algorithme ralentisse. Générer de bons bits aléatoires est difficile, donc la plupart des tables de hachage vont simplement pour des fonctions de hachage "raisonnablement bonnes", risquant des entrées dans le pire des CAs qui feront dégénérer les performances de l'algorithme.

Alors comment ces préoccupations en fait jouer dans la pratique? Eh bien, regardons les algorithmes. L'algorithme O(n)-time, O (n)-space fonctionne en construisant une table de hachage de tous les éléments dans le tableau de sorte que vous pouvez facilement vérifier si un élément donné est présent dans le tableau, puis balayage sur le tableau et de voir s'il ya une paire qui résume le total. Réfléchissons à la façon dont cet algorithme fonctionne étant donné les facteurs ci-dessus.

  • l'utilisation de la mémoire est O (n) et, en raison de la façon dont le hachage fonctionne, les accès à la table de hachage ne sont pas susceptibles d'être séquentielle (une table de hachage idéal aurait assez beaucoup les modèles d'accès aléatoires). Cela signifie que vous allez avoir beaucoup de défauts de cache.

  • l'utilisation élevée de la mémoire signifie que pour les entrées de grande taille, vous devez vous soucier de la mémoire qui est bippée à l'intérieur et à l'extérieur, ce qui exacerbe le problème ci-dessus.

  • en raison des deux facteurs ci-dessus, le terme constant caché dans L'exécution O(n) est probablement beaucoup plus élevé que il ressemble.

  • le malaxage n'est pas efficace dans le pire des cas, de sorte qu'il peut y avoir des entrées qui causent une dégradation importante de la performance.

maintenant, pensez à L'algorithme O(N log n)-time, O (1) space, qui fonctionne en faisant un tri en réseau en place (par exemple, tas port), puis en marchant vers l'intérieur à partir de la gauche et de la droite et voir si vous pouvez trouver une paire qui fait la somme à la cible. La deuxième étape de ce processus a une excellente localité de référence - pratiquement tous les accès aux tableaux sont adjacents - et à peu près tous les trous de cache que vous allez avoir vont être dans l'étape de tri. Cela augmentera le facteur constant caché dans la notation big-O. Cependant, l'algorithme n'a pas d'entrées dégénérées et sa faible empreinte mémoire signifie probablement que la localisation de référence sera meilleure que l'approche de la table de hachage. Donc, si je devais deviner, je mettrais mon argent sur cet algorithme.

... Eh bien, en fait, je mettrais mon argent sur un troisième algorithme: un algorithme O(N log n)-time, O(log n)-space qui est essentiellement l'algorithme ci-dessus, mais en utilisant introsort au lieu de heapsort. Introsort est un algorithme O(N log n)-time, O (log n)-space qui utilise quicksort aléatoire pour trier principalement le tableau, en passant à héapsort si le quicksort semble sur le point de dégénérer, et en faisant un dernier passage de tri d'insertion pour tout nettoyer. Quicksort a un site de référence étonnant - c'est pourquoi il est si rapide - et le tri d'insertion est plus rapide sur les petits intrants, c'est donc un excellent compromis. En outre, O (log n) mémoire supplémentaire est essentiellement rien - se rappeler, dans la pratique, log n est au plus 240. Cet algorithme a environ la meilleure localité de référence que vous pouvez obtenir, donnant un facteur constant très faible caché par le terme O(N log n), de sorte qu'il serait probablement plus performant que les autres algorithmes dans la pratique.

bien sûr, je dois aussi qualifier cette réponse. L'analyse que j'ai faite ci-dessus suppose que nous parlons de contributions assez importantes à la algorithme. Si vous regardez seulement de petites entrées, alors toute cette analyse sort par la fenêtre parce que les effets que je prenais en compte ne commenceront pas à apparaître. Dans ce cas, la meilleure option serait juste pour profil les approches et voir ce qui fonctionne le mieux. De là, vous pourriez être en mesure de construire une approche "hybride" où vous utilisez un algorithme pour les entrées dans une gamme de taille et un algorithme différent pour les entrées dans une gamme de taille différente. Il y a des Chances que cela donne une approche qui beats un seul des approches.

cela dit, pour paraphraser Don Knuth, "méfiez-vous de l'analyse ci-dessus - j'ai simplement prouvé correct, pas réellement essayé."La meilleure option serait de profil tout et voir comment il fonctionne. La raison pour laquelle je ne l'ai pas fait était de passer en revue l'analyse des facteurs à surveiller et de mettre en évidence la faiblesse d'une simple analyse big-O comparant les deux algorithmes. J'espère que la pratique en témoigne! Si non, j'aimerais les voir où je l'ai eu tort. : -)

28
répondu templatetypedef 2015-08-11 20:20:37

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)

6
répondu Kaganar 2015-08-11 22:08:11

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];
}
2
répondu Louis Ricci 2015-08-13 12:53:37

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.

2
répondu Shiva Kant Bhrighuvanshi 2015-08-17 07:06:35

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.

2
répondu gen-y-s 2015-08-17 08:03:28

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.

1
répondu 2015-08-18 15:16:53

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.

1
répondu Mehdi Karamosly 2015-08-18 16:11:49

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).

1
répondu 2015-08-18 18:42:16