Qu'est-ce que O(1) l'espace de la complexité?

Je vais avoir du mal à comprendre ce qui est en O(1) l'espace de la complexité. Je comprends que cela signifie que l'espace requis par l'algorithme ne se développe pas de l'entrée ou de la taille des données qui nous aide de l'algorithme. Mais que veut dire exactement?

Si nous utilisons un algorithme sur une liste liée dire 1->2->3->4, pour parcourir la liste pour atteindre les "3", nous déclare un pointeur temporaire. Et la traversée de la liste jusqu'à atteindre 3. Est-ce à dire, nous avons encore de O(1) en sus de l'espace? Ou signifie-t-il quelque chose de complètement différent. Je suis désolé si cela n'a pas de sens du tout. Je suis un peu confus.

o(1) l'espace de la complexité signifie que la quantité de mémoire que vous utilisez est constante et ne dépend pas de données qu'il est en cours de traitement, plus d'informations ici
ce n'est pas strictement vrai. Tout d'abord, vous écrit il y a peu-o, qui n'est pas la même que la grande-O. en Supposant que vous avez voulu dire Big-O: Supposons que vous avez une fonction qui prend un entier en entrée n, et il utilise 10 ko pour la même n et 20 ko pour impair n. Cette fonction prend O(1) de l'espace, mais il n'est certainement pas à prendre un quantité constante de l'espace. Ce n'est pas à confondre avec constante de l'espace, ce qui indique une constante limite supérieure, pas une constante montant.

OriginalL'auteur coder123 | 2017-04-06

  1. 23

    Pour répondre à votre question, si vous avez un pointeur et la traversée de la liste, il est compté comme O(1) l'espace de la complexité. Si vous avez 10 ou 100 ou même 1000 pointeurs de l'espace de la complexité est O(1). Mais, si vous voulez avoir du 'N' pointeurs, et même si " N " est aussi petit que 1, l'espace de la complexité est O(N).

    Espère que vous comprenez, O(1) correspond à une constante (10, 100 et 1000 sont constants) de l'espace et NE varie PAS en fonction de la taille de saisie (disons N).

    Que faut-il faire avec temporaire pointeurs et non temporaire des pointeurs?Merci d'avance pour réponse.
    Désolé, le mot n'est pas pertinent pour la réponse, donc à l'écart 🙂 Quand nous parlons de l'espace de la complexité, nous ne se soucient que l'espace de stockage utilisé au cours de l'exécution du programme.

    OriginalL'auteur Ajay Kumar

  2. 0

    Disons que je créer une certaine structure de données de taille fixe, et peu importe ce que je fais à la structure de données, il aura toujours la même taille fixe. Les opérations effectuées sur cette structure de données sont donc O(1).

    Un exemple, disons que j'ai un tableau de taille fixe de 100. Toute opération que je fais, si c'est de la lecture de la matrice ou de la mise à jour d'un élément, que l'opération sera O(1) sur le tableau. La taille du tableau (et donc la quantité de mémoire qu'il utilise) n'est pas en train de changer.

    Un autre exemple, disons que j'ai une LinkedList à laquelle j'ai ajouté des éléments. Chaque fois que j'ajoute un élément à la LinkedList, qui est un O(N) opération de la liste parce que je suis la croissance de la quantité de mémoire requise pour contenir tous les éléments ensemble.

    Espérons que cette aide!

    C'est un très mauvais exemple. Alors qu'un C tableau ne changent pas de taille whenoperations sont appliquées à ses membres, qui n'est pas vrai dans d'autres langues
    Je comprends, cet exemple s'applique au langage C et peuvent ne pas s'appliquer à la mise en œuvre des autres langues. Je vais ajouter une annexe à mon explication, une fois que j'ai le temps. Merci pour l'entrée @symcbean
    Ce n'est pas ce O(1) moyens. Un O(1) fonction n'a pas besoin d'utiliser un fixe taille pour toutes les entrées, il faut juste avoir une constante de la limite supérieure (espace) pour toutes les entrées. Par exemple, supposons que vous avez une fonction qui prend un entier en entrée n, et il utilise 10 ko pour la même n et 20 ko pour impair n. Cette fonction prend O(1) de l'espace, mais il n'est certainement pas à l'utilisation d'un taille fixe. Cependant, le limite supérieure est fixe, à 20 ko.

    OriginalL'auteur Matthew S