add(index,E) 방법의 실행 시간이 궁금합니다. javadoc에 따르면 추가 작업의 실행 시간은 O(1)으로 상각됩니다. 그러나 add(index,E)의 설명에 따르면arrayList의 인덱스에 요소를 삽입하기위한 실행 시간은 얼마입니까?
이 목록의 지정된 위치에 지정된 요소를 삽입합니다. 현재 해당 위치에있는 요소 (있는 경우) 및 오른쪽에있는 후속 요소를 이동 (해당 색인에 하나 추가)합니다.
따라서 O(N)처럼 보입니다. 이 수술을 위해 수술 시간이 O(1)이된다면, 우리는 무엇을 위해 무역해야하는지 궁금합니다. 이 작업을 수행 할 수있는 할부 상환 작업이 있습니까? O(1) 및 다른 작업을 위해 실행 시간이 희생 되었습니까?
나는 ArrayList 배열을 뒷받침하는 자바 데이터 구조를 변경하겠습니까?
ArrayList은 추가/제거의 임의 색인에 대해서는 O (n) 시간 복잡성이 있지만 목록 끝에있는 연산에 대해서는 O (1)입니다. O (1) 조회에 더 근접한은 이 Hash Table과 같은 데이터 구조를과 같을 수 있음을 나타냅니다. 삽입은 다시 크기 조정을 트리거하므로 O (n) 시간이 걸립니다.
배열 기반 목록을 순진하게 구현하면 각 항목을 삽입 할 때 별도의 작업으로 복사 할 수 있습니다. 다행히도 이동해야 할 바이트는 모두 메모리에서 연속적이며 모든 운영 체제는 빠른 속도로 단일 작업으로 많은 양의 메모리를 효율적으로 복사 할 수 있도록 지원합니다.
그래서 배열의 중간에 삽입하는 것은 생각만큼 나쁘지 않습니다. 물론 응용 프로그램에 올바른 종류의 액세스 패턴이있는 경우 데이터 구조를 연결된 목록으로 변경하는 것이 더 빠를 수도 있습니다.
데이터 구조를 연결 목록으로 변경하면 어떻게 도움이됩니까? O (1)이 동의하면 링크드리스트에 삽입되지만 O (N)을 삽입 할 위치를 찾는 것이 우리의 목적을 파괴하지는 않습니까? – tejas
따라서 "애플리케이션에 올바른 유형의 액세스 패턴이있는 경우"라는 경고가 표시됩니다. 예를 들어 목록을 보면서 현재 위치 또는 근처에 항목을 삽입하기로 결정한 항목을 기반으로하면 연결된 목록이 효과적입니다. 완전히 랜덤 액세스가 필요한 경우 링크 된 목록이 엉망입니다. – Rob
링크드리스트와 배열의 또 다른 측면은 크기 조정 중입니다. Java는 크기 조정 때문에 추가 작업에 대해 상각 된 O (1)을 얻습니다. – tejas
[일반 추가] (http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html#add (E))는 O (1), [인덱스에 추가] ] (http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html#add%28int,%20E%29)는 상각됩니다. O (N) –