Comment faire pour déterminer la mémoire et du temps de la complexité d'un algorithme?

Déterminer le moment et la mémoire complexités élève à comptage combien de ces deux ressources sont utilisées lors de l'exécution de l'algorithme, et de voir comment ces montants changer à mesure que la taille de saisie (k dans ce cas) des changements.

Temps va être déterminé par combien de fois chacune des instructions sont évalués, et un espace sera déterminé par la taille des structures de données concernées doivent obtenir pour calculer la solution.

Dans ce scénario particulier, vous êtes en train de regarder un algorithme récursif, donc, fondamentalement, cela implique de comptage 1) combien d'appels récursifs sont réalisés, et 2) la quantité de travail effectué pour chacun de ces appels.

Depuis l'entrée est réduit de moitié à chaque appel, la séquence d'appels va ressembler à quelque chose comme ceci:

sample(k)       )
 sample(k/2)    )
  sample(k/4)   ) 
     ...        ) - n = number of calls 
    sample(4)   )
     sample(2)  )
      sample(1) )

Réduire de moitié à chaque appel récursif de cette façon va conduire à une logarithmique nombre d'appels.

n = log(k)

À chaque appel, nous sommes le stockage d'un constante nombre de variables dans la pile d'appel, et de faire de la constante de la quantité de travail (opérations). Cela provient du fait que le nombre de variables et le nombre de comparaisons/ajouts/divisions dans chaque appel ne pas grossir avec de plus gros k.

Le temps total de la complexité est le nombre d'appels, multiplié par la quantité de travail effectué dans chaque appel, ainsi

time complexity = A*log(k) + B

Pour certaines constantes A et B, qui reflètent le temps réel coût d'un appel récursif et de faire des comparaisons/divisions respectivement. De la même façon:

space complexity = C*log(k) + D

Adapté pour les constantes C et D pour le coût de l'espace de la récursivité et de stockage variable respectivement.

Maintenant dans ce type d'analyse nous intéresse sur la complexité asymptotique, c'est que nous n'avons pas vraiment de soins sur les constantes, parce qu'elles reflètent des détails sur la machine qui exécute l'algorithme, et nous avons vraiment envie de savoir la forme de la courbe (comme k est plus grand). Si vous suivez les règles de l'écriture de la complexité à l'aide de Grand-Oh notation, vous arriverez à la suite:

space complexity = time complexity = O(log(k))

---

Edit: de Mémoire de la complexité des détails

Comme je l'ai dit avant, la mémoire de la complexité est déterminée par la taille des structures de données doivent obtenir pour calculer une solution, de sorte que vous pouvez demander: il n'existe pas de structures de données utilisées dans cette fonction, donc où est le log(k) de la mémoire?

La réponse courte: Vous avez à stocker log(k) différentes valeurs du paramètre k, un pour chaque appel récursif.

La réponse détaillée: il y a un implicite structure de données utilisée ici par le mécanisme de la fonction d'appel (qui nous exploiter via la récursivité) et son nom est le la pile des appels. Chaque fois sample(k) est appelé, une nouvelle trame de pile est créé et un certain nombre de valeurs sont poussés sur la pile: la valeur locale du paramètre k, l'adresse de retour, et d'autres dépendant de l'implémentation des choses. De cette façon, chaque appel récursif forme une "couche" sur la pile où son local, l'information est stockée. L'ensemble de l'image finit par ressembler à ceci:

----------- < top of stack
|  k = 1  |
|   ...   | < stack frame for sample(1)
|---------|
|  k = 2  |
|   ...   | < stack frame for sample(2)
|---------|

    ...

|---------|
| k = p/2 |
|   ...   | < stack frame for sample(p/2)
|---------|
|  k = p  |
|   ...   | < stack frame for sample(p)
|---------|
|         | < stack frame for main() or whatever 
              initially called sample(p) 
              (we don't count this one)

(J'ai distingué ici la première valeur du paramètre p à partir de la valeur de k à chaque appel récursif pour éviter toute confusion, nous l'espérons)

Principale chose à noter est, comme il y a n = log(k) appels récursifs, il y a n une telle pile d'images. Chaque frame de pile a taille constante, et donc l'espace de la complexité est O(log(k)).

OriginalL'auteur Ezequiel Muns