Java ArrayList의 시간 복잡도

Question

ArrayList은 java의 배열 또는 목록입니까? get 연산의 시간 복잡도는 무엇입니까? O(n) 또는 O(1)입니까?

Answer 1

ArrayList은 List이고 array입니다.

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

바로 ArrayList.get(index)의 자바 라이브러리 중 코드 :

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

기본적으로, 그냥 똑바로 보조 배열에서 값을 반환합니다. (RangeCheck(index))도 일정 시간)입니다

Answer 2

구현이 배열로 수행되고 get 작업은 O (1)입니다.

크기, IsEmpty 함수는, 세트, ​​ 반복자를 얻을, 및 listIterator의 처리는, 일정한 시간에 실행

의 javadoc는 말한다. 더하기 연산은 의 상각 된 상수 시간, 에서 실행됩니다. 즉, n 개의 요소를 추가 할 때마다 O (n) 시간이 필요합니다. 다른 모든 작업 은 선형 시간 (대략 말하기)로 실행됩니다. 상수 요소는 LinkedList 구현과 비교하여 에 비해 낮습니다.

Answer 3

현기증이있는 경우 배열로 뒷받침되는 List입니다. 그리고 예, get()의 시간 복잡도는 O (1)입니다.

Answer 4

모든 사람이 이미 지적했듯이, 작업이 일정 시간은 읽기 - O를 (1)하지만 쓰기 작업의 보조 배열에 공간이 재 할당을 실행할 수있는 잠재력을 가지고 있고,

크기, IsEmpty 함수는, 설정 얻을 반복자, 및 listIterator의 작업이 일정 시간에 실행 - 사본은 문서가 말한대로 그래서는 O (n) 시간에 실행됩니다. 추가 작업은 상각 된 상수 시간에 을 실행합니다. 즉, 에 n 요소를 추가하면 O (n) 시간이 필요합니다. 다른 모든 작업은 선형 시간 (대략 말하면서) 에서 실행됩니다. 상수 요소는 에 비해 LinkedList 구현에 비해 낮습니다.

실제로 용량이 모두 소모 될 때마다 보조 어레이가 두 배가되기 때문에 몇 가지 추가 후에 모든 것이 O (1)입니다. 그래서 배열이 16시에 시작되고, 꽉 차면 32, 64, 128 등으로 재 할당되므로 괜찮아 지지만 GC는 큰 realloc 중에 충돌 할 수 있습니다.

Answer 5

참고.

get(index) 방법은 O(1)

일정한 시간 그러나 우리는 인덱스를 알고있는 경우 그 경우입니다.indexOf(something)을 사용하여 색인을 얻으려고한다면 그 값은 O(n)