동적 배열 구현

Big O 표기법을 이해하고 있다고 가정합니다. 예제는 JavaScript에 있습니다. 정보 참고자료 Gayle Laakmann McDowell의 "코딩 인터뷰 크래킹"

소개

JavaScript나 Python과 같은 일부 언어에서는 배열의 크기가 자동으로 조정됩니다. 즉, 항목을 추가하면 배열의 크기도 커집니다. Java와 같은 다른 언어에서는 배열의 길이가 고정되어 있습니다. 즉, 배열을 초기화할 때 크기가 정의됩니다. 자동으로 커지는 이러한 배열을 동적 배열이라고 합니다.

동적 배열 이해

Java에서 ArrayList는 동적 크기 조정을 제공하면서도 을 제공하는 배열과 유사한 데이터 구조입니다. $O(1)$O(1) 입장. 배열이 가득 차면 배열 크기가 두 배로 늘어납니다. 두 배가 될 때마다 $O(n)$O(n) 그러나 매우 드물게 발생하므로 분할된 삽입 시간은 여전히 ​​입니다. $O(1)$O(1) .

다른 프로그래밍 언어에 따라 이 데이터 구조의 이름과 크기 조정 요소(Java에서는 2)가 다릅니다. 크기 조정 요소에 따라 배열 크기가 조정되는 정도가 결정됩니다.

분할 상환 삽입 시간이 필요한 이유 $O(1)$O(1) ?

크기를 조정할 때 크기 조정 요소가 2라고 가정하면 이전 배열(N의 절반)을 두 배로 늘려 크기 N의 배열로 증가하는 것을 관찰할 수 있습니다. 게다가 복사도 해야 합니다. $\mathrm{없음}\mathrm{/}2$N/2 이 새로운 배열에 요소를 추가합니다.

최종 용량 증가부터 첫 번째 용량 증가까지 복사하는 요소 수를 합산하면 다음과 같습니다. $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\frac{n}{16}+\mathrm{.}\mathrm{.}\mathrm{.}+2+1$ 2n​+4n​+8n​+16n​+...+2+1 이는 N보다 약간 작습니다. 따라서 N 요소를 삽입하는 데는 약 $O(n)$O(n) 전체적으로 일합니다. 각 삽입은 $O(1)$O(1) 평균적으로 일부 삽입에는 시간이 걸리더라도 $O(n)$O(n) 최악의 경우 시간.

핵심 개념과 Big O 복잡성

JavaScript의 동적 배열에는 일반적으로 각각 시간 복잡성이 다른 몇 가지 핵심 메서드가 있습니다.

get(i): 이 메소드는 인덱스 i에 있는 요소를 검색합니다.

• 복잡성: $O(1)$O(1)

set(i, n): 이 메소드는 인덱스 i의 요소를 n으로 설정합니다.

• 복잡성: $O(1)$O(1)

pushback(n): 이 메소드는 n 요소를 배열 끝에 추가합니다.

• 복잡성: $O(1)$O(1) 상각되었지만 $O(n)$O(n) 크기 조정이 발생할 때

popback(): 이 메서드는 배열의 마지막 요소를 제거합니다.

• 복잡성: $O(1)$O(1)

resize(): 이 메서드는 배열의 용량을 두 배로 늘리고 모든 요소를 ​​새 배열에 복사합니다.

• 복잡성: $O(n)$O(n)

getSize(): 이 메소드는 배열의 요소 수를 반환합니다.

• 복잡성: $O(1)$O(1)
• 참고: 크기 변수를 사용하여 배열의 채워진 슬롯 수를 추적하면 이러한 복잡성을 달성할 수 있습니다.

getCapacity(): 이 메소드는 어레이의 현재 용량을 반환합니다.

• 복잡성: $O(1)$O(1)

JavaScript로 구현

class DynamicArray {
    // size is # of filled slots while capacity is total slots in array
    constructor(capacity) {
        this.capacity = capacity;
        this.arr = new Array(this.capacity);
        this.size = 0;
    }

    // O(1)
    get(i) {
        if (i < 0 || i >= this.size) return undefined;
        return this.arr[i];
    }

    // O(1)
    set(i, n) {
        if (i < 0 || i >= this.size) return undefined;
        this.arr[i] = n;
    }

    // O(1) amortized 
    pushback(n) {
        if (this.size === this.capacity) {
            this.resize();
        }
        this.arr[this.size] = n;
        this.size++;
    }

    // O(1) 
    popback() {
        if (this.size === 0) return undefined;
        this.size--;
        let temp = this.arr[this.size];
        this.arr[this.size] = undefined;
        return temp;

    }

    // O(n)
    resize() {
        this.capacity *= 2;
        let newArr = new Array(this.capacity);
        for (let i = 0; i < this.size; i++) {
            newArr[i] = this.arr[i];
        }
        this.arr = newArr;
    }

    // O(1)
    getSize() {
        return this.size;
    }

    // O(1) 
    getCapacity() {
        return this.capacity;
    }
}

결론

동적 배열은 크기 조정 가능한 스토리지의 유연성과 지속적인 액세스의 효율성을 결합한 강력한 데이터 구조입니다. 이것이 도움이 되기를 바랍니다!

위 내용은 동적 배열 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!