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

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.

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.

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.

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.

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

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)

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.