Différences entre complexité temporelle et complexité spatiale?

j'ai vu que dans la plupart des cas la complexité du temps est liée à la complexité de l'espace et vice versa. Par exemple dans un tableau transversal:

for i=1 to length(v)
    print (v[i])
endfor

ici, il est facile de voir que la complexité de l'algorithme en termes de temps est O( n), mais il me semble que la complexité de l'espace est aussi n (également représenté comme O(n)?).

ma question:est-il possible qu'un algorithme ait une complexité temporelle différente de celle de l'espace?

44
demandé sur Ben N 2013-09-08 20:41:54

7 réponses

et espace les complexités ne sont pas liées entre elles. Ils sont utilisés pour décrire combien d'espace/temps votre algorithme prend basé sur l'entrée.

  • par exemple quand l'algorithme a espace complexité de:

    • O(1) - constant - l'algorithme utilise un fixe (petite) quantité d'espace qui ne dépend pas de l'entrée. Pour chaque taille de l'entrée de l'algorithme prendra le même (constant) montant de l'espace. C'est le cas dans votre exemple car l'entrée n'est pas prise en compte et ce qui compte c'est le temps/espace de print la commande.
    • O(n),O(n^2),O(log(n))... - ces indiquer que vous créez des objets en fonction de la longueur de votre entrée. Par exemple, créer une copie de chaque objet de v le stocker dans un tableau et l'imprimer après cela prend O(n) espace que vous créez n supplémentaires objet.
  • En revanche, le complexité décrit combien de temps votre algorithme consomme basé sur la longueur de l'entrée. Encore une fois:

    • O(1) - peu importe la taille de l'entrée, il faut toujours un temps constant - par exemple une seule instruction. Comme

      function(list l) {
          print("i got a list");
      }
      
    • O(n),O(n^2),O(log(n)) - encore une fois, il est basé sur la longueur de l'entrée. Pour exemple

      function(list l) {
           for (node in l) {
              print(node);
          }
      }
      

Notez que les deux derniers exemples prendre O(1) espace car vous ne créez rien. Comparez

function(list l) {
    list c;
    for (node in l) {
        c.add(node);
    }
}

ce qui prend O(n) espace parce que vous créez une nouvelle liste dont la taille dépend de la taille de l'entrée de façon linéaire.

votre exemple montre que la complexité temporelle et spatiale peut être différente. Il faut v.length * print.time pour imprimer tous les éléments. Mais l'espace est toujours la même - O(1) parce que vous ne créez pas d'objets supplémentaires. Donc, oui, il est possible qu'un algorithme ait une complexité temporelle et spatiale différente, car ils ne dépendent pas l'un de l'autre.

89
répondu stan0 2016-08-25 19:31:28

la complexité temporelle et Spatiale sont différents aspects du calcul de l'efficacité d'un algorithme.

complexité temporelle vise à découvrir comment le temps de calcul de un algorithme change avec le changement de la taille de l'entrée.

d'autre part, espace complexité permet de savoir combien (supplémentaire)de l'espace seraient requis par l'algorithme de changement dans la la taille de l'image.

Pour calculer la complexité temporelle de l'algorithme, la meilleure façon est de vérifier si nous avons augmentation de la taille de l'entrée, le nombre de comparaison(ou de calcul étapes) augmentent également et pour calculer l'espace de la complexité le meilleur pari est de voir l'exigence de mémoire supplémentaire de l'algorithme change aussi avec le changement de la taille de l'entrée.

Un bon exemple pourrait être de le tri des bulles.

disons que vous avez essayé de trier un tableau de 5 éléments. Dans le premier passage vous comparerez le 1er élément avec les 4 suivants. En second passage, vous comparerez le 2e élément avec les 3 suivants et vous continuerez cette procédure jusqu'à épuisement complet de la liste.

Maintenant ce qui se passera si vous essayez de trier 10 éléments. Dans ce cas, vous commencerez par comparer le 1er élément avec les 9 éléments suivants, puis le 2e avec les 8 éléments suivants et ainsi de suite. En d'autres termes, si vous avez n element array vous commencerez par comparer l'élément 1 avec les éléments N-1, puis 2 élément avec N-2 éléments et ainsi de suite. Il en résulte O(N^2) le temps de la complexité.

Mais qu'en taille. Lorsque vous avez trié 5 element ou 10 element array, avez-vous utilisé un tampon ou un espace mémoire supplémentaire. Vous pourriez dire Oui, j'ai utilisé une variable temporaire pour faire l'échange. Mais est-ce que le nombre de variables a changé quand vous avez augmenté la taille du tableau de 5 à 10. Non, quelle que soit la taille de l'input, vous utiliserez toujours une seule variable pour effectuer le swap. Eh bien, cela signifie que la taille de l'entrée n'a rien à voir avec l'espace supplémentaire, vous aurez besoin entraînant O(1) ou la complexité constante de l'espace.

fusion de tri

48
répondu Prateek 2016-05-11 19:20:42

tout d'abord, la complexité spatiale de cette boucle est O(1) (l'entrée n'est habituellement pas incluse dans le calcul de la quantité de stockage requise par un algorithme).

donc la question que j'ai est si c'est possible qu'un algorithme ait une complexité temporelle différente de la complexité spatiale?

Oui, il est. En général, le temps et la complexité de l'espace d'un algorithme ne sont pas liés entre eux.

Parfois, on peut être augmenté au détriment de l'autre. Ceci est appelé espace-temps compromis.

4
répondu NPE 2013-09-08 16:50:48

Oui, c'est certainement possible. Par exemple, le tri n nombres réels il faut O(n) de l'espace, mais O(n log n) fuseau. Il est vrai que la complexité de l'espace est toujours un limite inférieure à l'heure de la complexité, comme le temps d'initialiser l'espace est inclus dans le temps d'exécution.

4
répondu Mangara 2013-09-09 22:11:52
                            DTime(f) ⊆ DSpace(f)

où DTime (f) et DSpace (f) sont l'ensemble des langues reconnaissable par une machine de Turing déterministe dans le temps (respectivement, espace) O (f). C'est-à-dire que si un problème peut être résolu en temps O(f), alors il peut aussi être résolu dans l'espace O (f).

Moins évident est le fait que l'espace offre un lié au temps. Supposer que, sur un input de taille n, vous ayez à votre disposition des cellules de mémoire f(n) , comprenant des registres, des caches et tout. Après avoir écrit ces cellules possiblemoyens vous pourriez éventuellement arrêter votre calcul, dans le cas contraire, vous retourneriez une configuration vous déjà allés à travers, à partir de la boucle. Maintenant, sur un binaire alphabet, les cellules f (n) peuvent être écrites de 2^F(n) de différentes façons, ce qui donne notre temps limite supérieure: le calcul s'arrête en ce lié, ou vous pouvez forcer la résiliation, puisque le calcul ne s'arrêtera jamais.

Ceci est habituellement exprimé dans l'inclusion

                          DSpace(f) ⊆ Dtime(2^(cf))

pour un C. constant. la raison de la constante c est que si L est dans DSpace (f) vous savoir qu'il sera reconnu dans L'Espace O (f), alors que dans le précédent raisonnement, f était une limite réelle.

les relations ci-dessus sont subsumées par des versions plus fortes, impliquant non déterministe modèles de calcul, c'est la façon dont ils sont souvent déclaré dans les manuels (voir par exemple le théorème 7.4 dans le calcul Complexité par Papadimitriou).

4
répondu Andrea Asperti 2017-02-21 09:27:56

Parfois, oui ils sont liés, et parfois non, ils ne sont pas liés, en fait, nous utilisons parfois plus d'espace pour obtenir des algorithmes plus rapides comme dans la programmation dynamique https://www.codechef.com/wiki/tutorial-dynamic-programming la programmation dynamique utilise la memoization ou bottom-up, la première technique utilise la mémoire pour se souvenir des solutions répétées de sorte que l'algorithme n'a pas besoin de recalculer plutôt que de les obtenir à partir d'une liste de solutions. et l'approche ascendante commence avec le petites solutions et de construire sur pour atteindre la solution finale. Voici deux exemples simples, l'un montre la relation entre le temps et l'espace, et l'autre ne montrent aucune relation: supposons que nous voulons trouver la somme de tous les nombres entiers de 1 à un entier n: code1:

sum=0
for i=1 to n
   sum=sum+1
print sum

Ce code utilisé seulement 6 octets de mémoire j'=>2,n=>2 et somme=>2 octets par conséquent, la complexité temporelle est O(n), tandis que la complexité spatiale est O(1) code2:

array a[n]
a[1]=1
for i=2 to n
    a[i]=a[i-1]+i
print a[n]

ce code a utilisé au moins n*2 octets de la mémoire pour le tableau par conséquent, la complexité de l'espace est O(n) et la complexité du temps est aussi O (N)

1
répondu Ahmad Hassanat 2016-05-06 19:48:43

La manière dont l'espace de stockage requis par un algorithme varie avec la taille du problème est à résoudre. La complexité de l'espace est normalement exprimée en ordre de grandeur, par exemple O(N^2) signifie que si la taille du problème (N) double, alors quatre fois plus de stockage de travail sera nécessaire.

0
répondu Alam 2015-10-06 06:35:23