52
ArrayList은 java의 배열 또는 목록입니까? get 연산의 시간 복잡도는 무엇입니까? O(n) 또는 O(1)입니까?Java ArrayList의 시간 복잡도
A
답변
90
ArrayList은 List이고 array입니다.
get(index) 방법은 일정 시간, O(1), 작업입니다.
바로 ArrayList.get(index)의 자바 라이브러리 중 코드 :
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
기본적으로, 그냥 똑바로 보조 배열에서 값을 반환합니다. (RangeCheck(index))도 일정 시간)입니다
17
구현이 배열로 수행되고 get 작업은 O (1)입니다.
크기, IsEmpty 함수는, 세트, 반복자를 얻을, 및 listIterator의 처리는, 일정한 시간에 실행
의 javadoc는 말한다. 더하기 연산은 의 상각 된 상수 시간, 에서 실행됩니다. 즉, n 개의 요소를 추가 할 때마다 O (n) 시간이 필요합니다. 다른 모든 작업 은 선형 시간 (대략 말하기)로 실행됩니다. 상수 요소는 LinkedList 구현과 비교하여 에 비해 낮습니다.
3
현기증이있는 경우 배열로 뒷받침되는 List입니다. 그리고 예, get()의 시간 복잡도는 O (1)입니다.
9
모든 사람이 이미 지적했듯이, 작업이 일정 시간은 읽기 - O를 (1)하지만 쓰기 작업의 보조 배열에 공간이 재 할당을 실행할 수있는 잠재력을 가지고 있고,
크기, IsEmpty 함수는, 설정 얻을 반복자, 및 listIterator의 작업이 일정 시간에 실행 - 사본은 문서가 말한대로 그래서는 O (n) 시간에 실행됩니다. 추가 작업은 상각 된 상수 시간에 을 실행합니다. 즉, 에 n 요소를 추가하면 O (n) 시간이 필요합니다. 다른 모든 작업은 선형 시간 (대략 말하면서) 에서 실행됩니다. 상수 요소는 에 비해 LinkedList 구현에 비해 낮습니다.
실제로 용량이 모두 소모 될 때마다 보조 어레이가 두 배가되기 때문에 몇 가지 추가 후에 모든 것이 O (1)입니다. 그래서 배열이 16시에 시작되고, 꽉 차면 32, 64, 128 등으로 재 할당되므로 괜찮아 지지만 GC는 큰 realloc 중에 충돌 할 수 있습니다.
+2
입니다. 주제는 조금 벗어나지 만 누군가가 혼란스러워하고 정말로 강조하지 않는 것이 싫어합니다. ** ** ** 작업을합니다. –
+0
JDK 코드에서 (1.6.0_17) 새로운 용량은 실제로 (oldCapacity * 3)/2 + 1로 계산됩니다. – Adamski
+1
O (에서 쓰기 작업이 실행되는 것을 암시하는 것으로 보이는 첫 번째 문장에 대해 n) 시간. 그것은 의사가 말하는 것과 다르며, n 개의 원소를 더하기 위해서는 O (n) *이 필요하다고합니다. 개별 요소의 경우 삽입 시간은 여전히 O (1)입니다. 재 할당, 복사 등은 다소 "더 큰"O (1)로 만듭니다. –
0
참고.
get(index) 방법은 O(1)
일정한 시간 그러나 우리는 인덱스를 알고있는 경우 그 경우입니다.indexOf(something)을 사용하여 색인을 얻으려고한다면 그 값은 O(n)
입니다. array [n] ----은 시스템이 수학적 계산 = offsetvalue + (변수의 크기) * n을 의미하기 때문에 일정 시간입니다. . 그래서이 전체 계산은 메모리 위치에 다시 액세스하지 않고 프로세서에서 일어날 것입니다. 그 이유는 O (1) –