ArrayList : 삽입 대 지정된 요소의 삽입

Question

Arraylist를 고려하십시오. 내부적으로 전체가 아니며 지금까지 삽입 된 요소의 수를 알고 있습니다. 요소는 정렬되지 않습니다. ArrayList에 포함 된 요소 수에 관계없이 빠르면 아래에 나열된 작업을 선택하십시오. (즉, 구현하는 데 필요한 몇 가지 지침 만 필요함). 상기 (반드시 정렬되지 않은) 정수 배열

삭제 최대치 찾기 지정된 인덱스

로부터 데이터를 얻기 주어진 인덱스

에서

삽입

삽입 주어진 인덱스

지정된 인덱스의 요소 바꾸기

특정 요소 검색

지정한 색인에서 삽입을 선택하고 지정된 색인에서 데이터를 가져오고 요소를 바꾸지 만 대답 키는 삽입이라고 표시합니다. 필자가 일반적으로 이해하고있는 것처럼, ArrayList에서 삽입 작업을 수행하려면 요소가 모두 왼쪽으로 이동해야합니다. 목록의 시작 부분에이 작업을 수행하면 $ O (n) $ 시간의 복잡성이 발생합니다. 그러나 우리가 마지막에 그것을했다면 $ O (1) $가 될 것입니다.

내 질문에 온다 : (1) 무엇을 (있는 경우) 차이가 지정된 인덱스에 삽입하고 삽입 사이가와 (2) 삽입이 특정 시간 복잡도 주어진이 "빨리"로 간주되는 이유

Answer 1

먼저 첫 번째 방법을 보면 지금 java.util.ArrayList

public boolean add(E e) { 
    ensureCapacityInternal(size + 1); // Increments modCount!! 
    elementData[size++] = e; 
    return true; 
} 

public void add(int index, E element) { 
    rangeCheckForAdd(index); 

    ensureCapacityInternal(size + 1); // Increments modCount!! 
    System.arraycopy(elementData, index, elementData, index + 1, 
        size - index); 
    elementData[index] = element; 
    size++; 
} 

1. 에 정의 된 이러한 두 가지 방법을 살펴 (단지 추가 요소 : 큰 O 표기법에 대한 자세한 내용은

   ), 충분한 용량이 있는지 여부를 확인하고 을 추가하여 요소를 마지막 목록에 추가합니다.
   충분한 용량이 있다면이 작업에는 O(1) 시간 복잡성이 필요합니다. 그렇지 않으면 모든 요소가 이동해야하며 궁극적으로 시간 복잡성은 O(n)으로 증가합니다.

2. 두 번째 방법에서 index를 지정하면 해당 인덱스 뒤의 모든 요소가 이동하고 이전에는 이전보다 더 많은 시간이 걸릴 것입니다.

Answer 2

첫 번째 질문에 대한 대답은 이것이다 : i를 다음과 같은 모든 요소가 하나 개의 위치에 오른쪽으로 이동해야하는 것이기 때문에 지정된 인덱스 i에서

• 삽입은 O(n) 걸립니다.
• 한편, Java (ArrayList.add())에 구현 된 간단한 삽입은 요소가 배열의 끝에 추가되므로 변경이 필요하지 않으므로 O(1)이됩니다. 따라서 이동이 필요하지 않습니다.

두 번째 질문에서 간단한 삽입이 빠른 이유는 추가 작업이 필요하지 않으므로 시간이 일정하기 때문입니다.

Answer 3

(1)는 연속 요소 게다가, 어떤 경우에, 차이가 특정 인덱스에 삽입하고 삽입 사이에 존재하고

ArrayList를 저장한다. ArrayList의 끝 부분에 추가하면 ArrayList를 변경하지 않아도됩니다. 단, 자체 요소의 끝에 새 요소를 추가하는 경우는 예외입니다. 따라서이 작업은 O (1)이며 데이터 구조에서 작업을 반복적으로 수행하려는 경우에 유리한 일정한 시간을 사용합니다.

그러나 요소에 인덱스를 추가하려면 ArrayList를 사용하여 요소의 여유 공간을 확보해야합니다. 어떻게 된거 야? 삽입 된 요소 다음의 모든 요소는 새로운 삽입을위한 공간을 만들기 위해 한 단계 이동해야합니다. 색인은 첫 번째 요소와 n 번째 요소 사이에있는 항목입니다 (포괄적으로). 따라서이 연산은 기껏해야 O (1)이고 최악의 경우 O (n)입니다. 여기서 n은 배열의 크기입니다. 큰 목록의 경우 O (n)은 O (1)보다 훨씬 오래 걸립니다.

(2)의 삽입을 위해 특정 시간 복잡도 주어진 그것은 O (1), 또는 일정 시간 때문에

가 그것은 빠른 여겨진다 "빠른"으로 인식되는 이유. 시간 복잡도가 실제로 하나의 연산 일 경우 가능한 한 빠르며 다른 작은 상수도 빠르게 간주되며 O (1)에 의해 동등하게 표기됩니다. 여기서 "1"은 단 하나의 연산만을 의미하지는 않습니다 ,하지만 작업의 양을 다른 크기에 의존하지 않는, 귀하의 예제에서 ArrayList의 크기가 될 것이라고. 그러나 일정 시간 복잡도는 큰 상수를 포함 할 수 있지만 일반적으로 가능한 한 가장 빠른 시간 복잡성으로 간주됩니다. 이를 컨텍스트에 넣기 위해, O (1) 연산은 1000 개의 원소를 가진 ArrayList에서 대략 1 * k 연산을 수행하는 반면 O (n) 연산은 대략 1000 * k 연산을 필요로합니다. 여기서 k는 일정한 상수입니다.

Big-O 표기법은 동작 또는 전체 프로그램을 실행할 때 실행할 작업 수를 측정하는 척도로 사용됩니다. What is a plain English explanation of "Big O" notation?

Answer 4

ArrayList는 내부적으로 추가 할 때 증가 된 크기의 새 배열을 만들려고 Array.copyOf을 사용하는 배열 자체이지만 원래 내용은 그대로 유지합니다. 삽입에 대한 간단한 추가 (배열 끝에 데이터를 추가) 또는 첫 번째 (0 번째) 인덱스에 관계없이 단순성을 염두에두면 대부분의 데이터 구조가 더 빠를 것입니다. 데이터 구조

단순한 추가는 순회를 필요로하지 않지만 색인에 추가하는 것은 삭제와 마찬가지로 요소를 왼쪽으로 이동해야합니다. 그것은 System.arrayCopy을 사용하여 하나의 배열을 다른 배열로 복사하여 인덱스와 데이터를 변경합니다.

그렇다면 간단한 삽입은 색인 삽입보다 빠릅니다.