Zoals te zien in de documentatie voor TimeComplexity, het list-type van Python is geïmplementeerd, gebruikt een array.
Dus als een array wordt gebruikt en we doen een paar toevoegingen, moet je uiteindelijk de ruimte opnieuw toewijzen en alle informatie naar de nieuwe ruimte kopiëren.
Hoe kan het tenslotte O(1) in het slechtste geval zijn?
Antwoord 1, autoriteit 100%
Het wordt afgeschreven op O(1), niet op O(1).
Stel dat de gereserveerde grootte van de lijst 8 elementen is en dat deze verdubbelt als de ruimte opraakt. Je wilt 50 elementen pushen.
De eerste 8 elementen drukken O(1) in.
De negende triggert hertoewijzing en 8 kopieën, gevolgd door een O(1)-push.
De volgende 7 druk O(1) in.
De zeventiende triggert hertoewijzing en 16 kopieën, gevolgd door een O(1)-push.
De volgende 15 druk O(1) in.
De drieëndertigste triggert hertoewijzing en 32 kopieën, gevolgd door een O(1)-push.
De volgende 17 druk op O(1).
Dus alle pushes hebben O(1) complexiteit, we hadden 56 exemplaren bij O(1) en 3 hertoewijzingen bij O(n), met n = 8, 16 en 32. Merk op dat dit een geometrische reeks en is asymptotisch gelijk aan O(n) met n = de uiteindelijke grootte van de lijst. Dat betekent dat de hele operatie om n objecten op de lijst te plaatsen O(n) is. Als we dat per element afschrijven, is het O(n)/n = O(1).
Antwoord 2, autoriteit 47%
Als je naar de voetnoot kijkt in het document dat je hebt gelinkt, kun je zien dat ze een waarschuwing bevatten:
Deze operaties zijn gebaseerd op het gedeelte ‘Afgeschreven’ van ‘Amortized Worst
Case”. Individuele acties kunnen verrassend lang duren, afhankelijk van de
geschiedenis van de container.
Met behulp van afgeschreven analysekunnen we, zelfs als we af en toe dure operaties moeten uitvoeren, een ondergrens van de ‘gemiddelde’ kosten van bewerkingen wanneer u ze als een reeks beschouwt, in plaats van afzonderlijk.
Dus elke afzonderlijke bewerking kan erg duur zijn – O(n) of O(n^2) of iets nog groters – maar aangezien we weten dat deze bewerkingen zeldzaam zijn, garanderen we dat een reeks O(n)-bewerkingen kan worden gedaan in O(n) tijd.
Antwoord 3
Dit is heel eenvoudig.
We kunnen dit berekenen door de totale tijd van het toevoegen van n elementen in een arraylijst op te tellen en te delen door n.
Ten eerste moeten we log(n) tijden verplaatsen, en elke verplaatsing wordt verdubbeld met 2. Dus we hebben een proportionele reeks waarvan de verhouding 2 is, en de lengte is log(n).
De som van een proportionele reeks is a(1-r^n)/(1-r)
Dus de totale verplaatsingstijd is (1-n)/(1-2)=n
De tijdscomplexiteit zou n/n=1 zijn.