In einer Stapelüberlaufantwort , warum ArrayList.get O (1) und nicht O (n) Der Responder sagte, dass ArrayList von einem Array und einem bestimmt die konstante Zeitkomplexität statt linear! Ich versuche, meinen Kopf darum zu wickeln, wird nicht jedes Array zu mindestens einer Teilsuche über vielleicht ein Alter von n Feldern in einem Array haben und somit irgendwie eine O (n) Suche bilden (wenn das Element gejagt wird) ist in der n-1 Position des Arrays - wird dies nicht eine O (n) Suche sein? Es ist immer noch eine Schleife mit einer Ebene, die ich für O (n) Komplexität hielt?
Arrays werden sequenziell im Speicher abgelegt. Das heißt, wenn es sich um ein Array von Ganzzahlen handelt, die jeweils 4 Byte verwenden und bei der Speicheradresse 1000 beginnt, ist das nächste Element bei 1004 und dann bei 1008 und so weiter. Wenn ich also das Element an Position 20 in meinem Array haben möchte, muss der Code in get() berechnen:
um die genaue Speicheradresse des Elements zu haben. Nun, RAM-Speicher haben ihren Namen von Random Access Memory, weil sie so aufgebaut sind, dass sie eine Hierarchie von Hardware-Multiplexern haben, die es ihnen erlauben, auf jede gespeicherte Speichereinheit (Byte?) In konstanter Zeit zuzugreifen, gegeben die Adresse.
Somit wird von zwei einfachen arithmetischen Operationen und einem Zugriff auf den RAM O (1) gesagt.
Als Antwort wie vorgeschlagen:
ArrayList.get(int) sucht nicht . Es gibt direkt das Element zurück, das durch den gelieferten Index adressiert wird ... Genau wie bei einem Array - daher der Name.
ArrayList.get (int) Quelle:
%Vor%Wobei rangeCheck (int) ist:
%Vor%Und elementData () ist:
%Vor% Eine Verknüpfte Liste hätte jedoch eine O(n) get: Sie müsste zum nächsten Element springen, bis der gewünschte Index erreicht ist ...
Wo entry (int) ist ( das macht es zu O (n) ):
%Vor%(Hinweis: Es handelt sich um eine doppelt verkettete Liste, daher sparen Sie sich Zeit, indem Sie den Endpunkt auswählen, der dem gewünschten Ergebnis am nächsten kommt, aber dies ist immer noch O (n))
Der Zugriff auf einen bestimmten Index in einem Array ist eine konstante Zeitoperation, da dabei die Basisspeicheradresse vom Array-Objekt abgerufen und auf den Speicher bei Basisadresse + Index multipliziert mit der Größe des Elementtyps zugegriffen wird. Da alle Elemente dazwischen übersprungen werden, ist die Zugriffszeit durch eine Konstante gebunden.
Die ArrayList.get(int) -Methode ist ein dünner Wrapper über einen direkten Array-Zugriff, daher ist sie auch durch eine Konstante begrenzt.