Временная сложность для java ArrayList
ArrayList массив или список в Java? то, что является временной сложностью для получить операции, является ею O(n) или O(1)?
4 ответа
EDIT Этот ответ был написан на 2010 языке и работал в то время. Более современное решение можно найти в ответе Алекса Миллера.
Какой код вызывается из Java? Если класс создан с помощью gen-class, просто вызовите его. Если требуется вызвать функцию из сценария, обратитесь к в следующем примере .
Если вы хотите вычислить код из последовательности, в Java, то вы можете использовать следующий код:
import clojure.lang.RT;
import clojure.lang.Var;
import clojure.lang.Compiler;
import java.io.StringReader;
public class Foo {
public static void main(String[] args) throws Exception {
// Load the Clojure script -- as a side effect this initializes the runtime.
String str = "(ns user) (defn foo [a b] (str a \" \" b))";
//RT.loadResourceScript("foo.clj");
Compiler.load(new StringReader(str));
// Get a reference to the foo function.
Var foo = RT.var("user", "foo");
// Call it!
Object result = foo.invoke("Hi", "there");
System.out.println(result);
}
}
Чтобы быть педантичным, это список , поддерживаемый массивом. И да, сложность времени для get () равна O (1).
ArrayList в Java - это список , который поддерживается массивом .
Метод get (index) - это постоянное время, O (1) , операция.
Код непосредственно из библиотеки Java для ArrayList.get (index) :
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
В основном он просто возвращает значение непосредственно из резервного массива. ( Проверка (индекс) ) также является постоянным временем)
Это реализация выполняется с массивом, а операция Get - O (1).
Javadoc говорит:
Размер, испуганный, Get, Set, Итератор, и операции Listeriator работают в постоянном время. Add Operation работает в амортизированное время постоянного времени , То есть добавление n элементов требует o (n) времени. Все другие операции бегать в линейном времени (грубо говоря). Постоянный фактор низкий по сравнению Для этого для реализации LinkedList.
Как и все уже указали, операции чтения являются постоянными временем - o (1), но операции записи имеют возможность заканчиваться пространством в массиве резервного копирования, повторное распределение и копию - так что работает в O (n) время, как говорит Док:
Размер, ustemby, Get, Set, iTerator, и операции listeristor работают в постоянное время. Операция Add Run в амортизированном постоянном времени, то есть Добавление n элементов требует o (n) времени. Все другие операции работают в линейное время (грубо говоря). То постоянный фактор низкий по сравнению с что для LinkedList выполнение.
На практике все равно (1) после нескольких добавок, поскольку массив поддержки удвоится каждый раз, что его емкость исчерпана. Таким образом, если массив начинается в 16, становится полным, он перераспределяется до 32, затем 64, 128 и т. Д. Так что масштабируется в порядке, но GC может ударить во время большого Realloc.
, чтобы быть педантичным, это список , поддерживаемый массив. И да, момент сложности для GET () - это o (1).