52
Czy ArrayList jest tablicą lub listą w java? jaka jest złożoność czasu dla operacji pobierania, czy jest to O(n) lub O(1)?Złożoność czasu dla java ArrayList
A
Odpowiedz
90
Numer ArrayList w języku Java to List, który jest obsługiwany przez array.
Metoda get(index) to stała godzina, O(1), operacja.
Kod prosto z biblioteki Java dla ArrayList.get(index):
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
Zasadniczo, po prostu zwraca wartość prosto z tablicy podkładowej. (RangeCheck(index)) jest również stały czas)
17
Implementacja odbywa się za pomocą tablicy, a operacja get to O (1).
javadoc mówi:
Wielkość, isEmpty, get, set, iterator, a operacje listIterator prowadzony w ciągłym czasie. Operacja dodawania działa w zamortyzowanym stałym czasie, , czyli dodanie n elementów wymaga O (n) czasu. Wszystkie inne operacje są uruchamiane w czasie liniowym (w przybliżeniu). Stały współczynnik jest niski w porównaniu z do tego dla implementacji LinkedList.
3
Aby być pedantycznym, jest to List poparte tablicą. I tak, złożoność czasu dla get() to O (1).
9
Jak już wszyscy zauważyli, operacje odczytu są stałe czas - O (1), ale operacje zapisu mają potencjał, aby zabrakło miejsca w tablicy backing, ponowne przydzielenie i kopia - tak, że biegnie w O (n) czasie, gdy doc mówi:
wielkość, isEmpty, get, set, iterator, i operacje listIterator uruchomić w stałym czasie. Operacja add działa w zamortyzowanym czasie stałym, czyli dodanie n elementów wymaga O (n) czasu. Wszystkie inne operacje wykonywane są w liniowym czasie (w przybliżeniu). Współczynnik stały jest niski w porównaniu do , który dotyczy implementacji LinkedList .
W praktyce wszystko jest O (1) po kilku dodaniach, ponieważ tablica podkładu jest podwojona za każdym razem, gdy wyczerpana jest pojemność. Więc jeśli tablica zaczyna się od 16, staje się pełna, to jest ponownie przydzielona do 32, a następnie 64, 128 itd., Więc skaluje się w porządku, ale GC może trafić podczas dużego ponownego przydziału.
+2
To trochę poza tematem, ale nie chciałbym, aby ktoś się zmieszał i nie zauważył w operacjach ** get **. –
+0
W kodzie JDK, którego szukam (1.6.0_17), nowa pojemność jest obliczana jako (oldCapacity * 3)/2 + 1. – Adamski
+1
Kwestionować pierwsze zdanie, co wydaje się sugerować, że operacje zapisu są wykonywane w O (n) czas. To nie jest to, co mówi doktor, mówi, że * dodawanie n elementów wymaga O (n) *. Dla poszczególnych elementów czas wstawienia nadal wynosi O (1). Ponowne przydzielenie, kopiowanie itp. Powoduje, że jest to nieco "większy" O (1). –
0
Tylko uwaga.
Sposób get(index) jest stałą czasową, O(1)
Ale to w przypadku, gdy znamy indeks.Jeśli spróbujemy uzyskać indeks przy użyciu indexOf(something), będzie to kosztować O(n)
Jest to stały czas, ponieważ array [n] ---- oznacza, że system po prostu wykona obliczenie matematyczne = offsetvalue + (wielkość zmiennej) * n . więc to całe obliczenie stanie się w procesorze bez uzyskania dostępu do lokalizacji pamięci wielokrotnie. Dlatego jest to O (1) –