Java ArrayList의 시간 짜고

Java ArrayList의 시간 짜고

---

가 ArrayList배열이나 자바의 목록은? 그것을 가져 오기 오기 작업에 대한 시간 복잡도 것입니다 O(n)나 O(1)?

---

ArrayList자바는이다 List에 의해 뒷받침된다 array.

이 get(index)방법은 시간 O(1),, 작업입니다.

다음에 대한 Java 라이브러리에서 바로 나온 코드 ArrayList.get(index):

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

기본적으로 백업 배열에서 바로 값을 반환합니다. ( RangeCheck(index))도 일정 시간입니다)

---

구현은 배열로 이루어집니다 get 작업은 O (1)입니다.

javadoc 말한다 :

size, isEmpty, get, set, iterator 및 listIterator 작업은 다음 시간에 실행됩니다. 작업은 추가 상각 된 상수 time-으로 실행됩니다 . 즉, n 개의 추가 요소를 추가해야 O (n) 시간이 필요합니다. 다른 모든 작업은 선형 시간으로 실행됩니다 (대략적으로 말하면). 상수 인자는 LinkedList 구현에 비해 낮습니다.

---

모두가 이미 지적했듯이 읽기 작업은 오늘 시간 (O (1))이지만 쓰기 작업은 백업 배열, 재 할당 및 복사본의 공간이 부족할 가능성이 있으므로 O (n) 시간에 실행됩니다. , 문서에 따르면 :

size, isEmpty, get, set, iterator 및 listIterator 작업은 다음 시간에 실행됩니다. 추가 작업은 상각 된 일정 시간에 실행됩니다. 즉, n 개의 추가 요소를 추가해야 O (n) 시간이 필요합니다. 다른 모든 작업은 선형 시간으로 실행됩니다 (대략적으로 말하면). 상수 인자는 LinkedList 구현에 비해 낮습니다.

고갈 될 때마다 두 배가되기 때문에 몇 번 추가하면 모든 것이 O (1)입니다. 따라서 배열이 16에서 시작하여 가득 차면 32, 64, 128 등으로 재 할당 할당 확장이 가능하지만 큰 재 할당 중에 GC가 보관 수 있습니다.

---

현명하게 말하면 List배열 로 뒷받침됩니다. 그리고 네, 시간 복잡도 get()는 O (1)입니다.

---

그냥 메모.

get(index)방법은, 시간이고O(1)

그러나 우리가 지수를 안다면 그것은 사실입니다. 을 사용하여 색인을 얻으려고 indexOf(something)하면 비용이 발생합니다.O(n)

참고 URL : https://stackoverflow.com/questions/2182597/time-complexity-for-java-arraylist