J'ai une question que:Tableau Espace complexité
J'ai un tableau "S" qui a n objets en elle. chaque objet a également m champs. Je veux enregistrer certains d'entre eux dans l'autre tableau comme "Q". Je veux savoir que la complexité de l'espace de cette méthode facile est O(|Q|)?
La taille S est n*sum(sizeofeach(m of n))
Supposons donc que vous enregistrez l'objet r où r<n
La taille de q il est r*(sum(sizeofeach(m of r))
La complexité de l'espace est la quantité d'espace nécessaire pour stocker Q Soit s la taille d'un élément dans Q, c'est-à-dire s = size of all m fields. La complexité de l'espace est O(n*s). Si tous les champs ont la même taille constante, vous pouvez dire O(n*m).
Il n'est donc pas correct d'écrire O (r)? – user472221
Je ne pense pas que la complexité est utilisée pour l'espace mémoire, elle est utilisée pour le temps de traitement. –
par exemple la complexité de l'espace pour le tri par fusion est O (n) qui appartient à l'espace mémoire (je pense) – user472221