5 ответов
ArrayList в Java List, который поддерживается array.
get(index) метод является постоянным временем, O(1), операция.
код прямо из библиотеки Java для ArrayList.get(index):
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
В основном, это просто возвращает значение прямо из вспомогательного массива. (RangeCheck(index)) также постоянное время)
Чтобы быть педантичным, это List поддержано массивом. И да, временная сложность для get() является O (1).
Это - реализация, сделан с массивом, и получить операция является O (1).
javadoc говорит:
размер, isEmpty, получает, установил, итератор и listIterator операции, выполненные в постоянное время. Добавить операционные выполнения в амортизировали постоянное время , то есть, добавление n элементы требует O (n) время. Все другие операции выполняются в линейное время (примерно говорящий). Постоянный множитель является низким по сравнению с этим для реализации LinkedList.
Как все уже указали, операции чтения являются постоянным временем - O (1), но операции записи имеют потенциал для исчерпывания пространства во вспомогательном массиве, перераспределении и копии - так, чтобы выполнения в O (n) время, как в документе говорится:
размер, isEmpty, получает, установил, итератор и listIterator операции, выполненные в постоянное время. добавить операционные выполнения в амортизируемое постоянное время, то есть, добавляя n элементы требует O (n) время. Все другие операции, выполненные в линейное время (примерно говорящий). Постоянный множитель является низким по сравнению с этим для реализации LinkedList.
На практике все - O (1) после того, как некоторые добавляют, так как вспомогательный массив удвоен каждый раз, когда это - способность, исчерпывается. Таким образом, если массив запускается в 16, становится полным, он перераспределен к 32, тогда 64, 128, и т.д. таким образом, он масштабируется хорошо, но GC может подбросить ударом во время большого перевыделения.
Просто Примечание.
get(index) метод является постоянным временем, O(1)
, Но это имеет место, если мы знаем индекс. Если мы пытаемся получить индекс с помощью indexOf(something), который будет стоить O(n)