Ik heb moeite om te begrijpen wat O(1) ruimtecomplexiteit is. Ik begrijp dat dit betekent dat de ruimte die het algoritme nodig heeft niet meegroeit met de invoer of de grootte van de gegevens waarop we het algoritme gebruiken. Maar wat betekent het precies?
Als we een algoritme gebruiken op een gekoppelde lijst, zeg 1->2->3->4, om de lijst te doorlopen om “3” te bereiken, declareren we een tijdelijke aanwijzer. En doorloop de lijst totdat we 3 bereiken. Betekent dit dat we nog O(1) extra ruimte hebben? Of betekent het iets heel anders. Het spijt me als dit helemaal geen zin heeft. Ik ben een beetje in de war.
Antwoord 1, autoriteit 100%
Om je vraag te beantwoorden, als je een traversal-algoritme hebt voor het doorlopen van de lijst die een enkele aanwijzer toewijst om dit te doen, wordt aangenomen dat de traversal-algoritmen O(1) ruimtecomplexiteit hebben. Bovendien, laten we zeggen dat het traversal-algoritme niet 1 maar 1000 pointers nodig heeft, de ruimtecomplexiteit wordt nog steeds beschouwd als O(1).
Echter, laten we zeggen om de een of andere reden, het algoritme moet ‘N’ pointers toewijzen bij het doorlopen van een lijst met grootte N, dwz het moet 3 pointers toewijzen voor het doorlopen van een lijst van 3 elementen, 10 pointers voor een lijst met 10 elementen, 1000 pointers voor een lijst van 1000 elementen enzovoort, dan wordt aangenomen dat het algoritme een ruimtecomplexiteit heeft van O(N). Dit geldt zelfs als ‘N’ erg klein is, bijv. N=1.
Om de twee bovenstaande voorbeelden samen te vatten: O(1) staat voor constant ruimtegebruik: het algoritme wijst hetzelfde aantal pointers toe, ongeacht de grootte van de lijst. O(N) daarentegen staat voor lineair ruimtegebruik: het ruimtegebruik van het algoritme groeit samen met de invoergrootte.
Antwoord 2
Het is gewoon de hoeveelheid geheugen die door een programma wordt gebruikt. de hoeveelheid computergeheugen die het hoofdgeheugen is dat het algoritme nodig heeft om de uitvoering te voltooien met betrekking tot de invoergrootte.
Space Complexity(s(P))van een algoritme is de totale ruimte die het algoritme in beslag neemt om de uitvoering te voltooien met betrekking tot de invoergrootte. Het bevat zowel constante ruimte als hulpruimte.
S(P) = Constante ruimte + hulpruimte
Constante ruimte is de ruimte die is vastgesteld voor dat algoritme en is over het algemeen gelijk aan ruimte die wordt gebruikt door invoer- en lokale variabelen. Auxiliary Space is de extra/tijdelijke ruimte die door een algoritme wordt gebruikt.
Antwoord 3
Stel dat ik een datastructuur maak met een vaste grootte, en wat ik ook doe met de datastructuur, deze zal altijd dezelfde vaste grootte hebben. Bewerkingen uitgevoerd op deze datastructuur zijn daarom O(1).
Een voorbeeld, laten we zeggen dat ik een array heb met een vaste grootte van 100. Elke bewerking die ik doe, of dat nu het lezen van de array is of het bijwerken van een element, die bewerking is O(1) op de array. De grootte van de array (en dus de hoeveelheid geheugen die het gebruikt) verandert niet.
Nog een voorbeeld, laten we zeggen dat ik een LinkedList heb waaraan ik elementen toevoeg. Elke keer dat ik een element aan de LinkedList toevoeg, is dat een O(N)-bewerking aan de lijst omdat ik de hoeveelheid geheugen die nodig is om alle elementen bij elkaar te houden, vergroot.
Hopelijk helpt dit!