Złożoność czasowa dla java ArrayList
Jest ArrayList tablicą czy listą w Javie? jaka jest złożoność czasowa operacji get, czy to O(n) Czy O(1)?
5 answers
An ArrayList w języku Java jest List, który jest wspierany przez array.
Metoda get(index) to stała czasowa, O(1), operacja.
Kod prosto z biblioteki Javy dla ArrayList.get(index):
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
W zasadzie, po prostu zwraca wartość prosto z tablicy pomocniczej. (RangeCheck(index)) jest również stałym czasem)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-02 08:16:10
Implementacja odbywa się za pomocą tablicy, a operacja get to O(1).
Javadoc says:
The size, isEmpty, get, set, iteratora, a operacje listeratora przebiegają w stałej czas. Operacja add działa w zamortyzowanym stałym czasie , oznacza to, że dodanie n elementów wymaga czasu O (n). Wszystkie pozostałe operacje uruchom w czasie liniowym(z grubsza rzecz biorąc). Współczynnik stały jest niski w porównaniu do tego dla implementacji LinkedList.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-02 08:16:20
Jak już wszyscy zauważyli, operacje odczytu to stały czas-O(1), ale operacje zapisu mają potencjał, aby zabrakło miejsca w tablicy pomocniczej, re-alokacji i kopii - tak, że działa w czasie O (n) , jak mówi dokument:
Rozmiar, isEmpty, get, set, iterator, i operacje listeratorowe przebiegają w stały czas. operacja dodaj działa w amortyzowanym stałym czasie, czyli, dodanie n elementów wymaga czasu O (n). Wszystkie pozostałe operacje przebiegają w czas liniowy (z grubsza rzecz biorąc). Na współczynnik stały jest niski w porównaniu do że na LinkedList wdrożenie.
W praktyce wszystko jest O(1) po kilku dodaniach, ponieważ tablica nośna jest podwojona za każdym razem, gdy jej pojemność jest wyczerpana. Więc jeśli tablica zaczyna się od 16, zapełni się, zostanie ponownie przydzielona do 32, następnie 64, 128 itd. więc skaluje się dobrze, ale GC może podbić podczas dużego realloc.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-02 08:18:53
Aby być pedantycznym, jest to List wspierane przez tablicę. I tak, złożoność czasowa get() wynosi O (1).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-02 08:10:31
Tylko notkę.
Metoda get(index) jest stała czasu, O(1)
indexOf(something), będzie to kosztować O(n)Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-02-02 09:23:35