배열의 맨 뒤에 데이터를 삽입 / 삭제 하는 경우 : O(1)
배열의 끝 주소 = 시작 주소 + (1칸이 차지하는 주소 X 배열 길이)
위 수식을 통해 배열의 끝 주소를 찾고, 배열의 길이를 1 증가시킨 후, 추가할 원소 데이터를 저장하면 된다.
그러므로 시간복잡도는 O(1)이다.
위에서 알아본 배열의 가장 끝에 원소 추가하기와 비슷하게 배열의 끝 주소를 찾고, 배열의 길이를 1만큼 줄이면 되므로 시간복잡도는 O(1)이다.
배열의 맨 뒤를 제외한 경우의 위치에 데이터를 삽입 / 삭제 하는 경우 : O(N)
임의의 위치에 원소를 새로 추가해서 끼워넣으려면 그 뒤에 존재하는 모든 원소들을 한 칸씩 뒤로 밀어야 한다.
뒤로 미는 연산이 한 번 일어날 때 O(1)이 걸린다. 만약 N개의 원소를 한 칸씩 밀어야 한다면 O(1XN) = O(N)이 걸리게 된다.
추가하려는 위치가 배열의 끝과 가까울수록 그 뒤에 존재하는 원소의 개수가 적어져 뒤로 밀어내는 연산의 수도 줄어든다.
평균적으로 N/2 개의 원소를 뒤로 밀어내야 하므로 시간복잡도는 O(N/2) = O(N)이다.
삭제 연산도 임의의 위치에 원소를 추가하는 것과 비슷하게 수행된다.
임의의 위치에 있는 원소를 삭제하면 그 뒤에 존재하는 모든 원소들을 한 칸씩 앞으로 당겨와야 한다.
왜 굳이 앞으로 당겨와야 할까?
배열의 정의 상 배열은 메모리의 데이터(원소)를 연속하게 배치한 자료구조이기 때문이다.
앞으로 당기는 연산이 한 번 일어날 때 O(1)이 걸린다. 만약 N개의 원소를 한 칸씩 앞으로 당겨야 한다면 O(1XN) = O(N)이 걸리게 된다.
제거하려는 원소의 위치가 배열의 끝과 가까울수록 그 뒤에 존재하는 원소의 개수가 적어져 앞으로 당기는 연산의 수도 줄어든다.
반대로 제거하려는 위치가 배열의 처음과 가까울수록 그 뒤에 존재하는 원소의 개수가 많아져 앞으로 당기는 연산의 수도 늘어난다.
평균적으로 N/2 개의 원소를 앞으로 당겨야 하므로 시간복잡도는 O(N/2) = O(N)이다.
배열의 특정 위치 데이터를 탐색하는 경우 : O(1)
메모리 상에 일렬로 나열되어 있으니 배열의 시작 주소에서 k칸 만큼 더하면 k번째 원소를 찾을 수 있다.
k번째 원소의 위치 = 시작주소 + (1칸이 차지하는 주소 X k)
단순 사칙연산 계산에 의해 O(1)만에 k번째 원소를 찾을 수 있다.
'use strict';
class Array {
constructor() {
// 배열의 빈 공간을 제외한 데이터들의 개수
this.length = 0;
this.data = [];
}
// 배열의 원소 탐색
// 인덱스를 알고 있다면 특정 원소에 접근하는 시간 복잡도는 O(1)이다.
get(idx) {
console.log(this.data[idx]);
}
// 배열의 맨 뒤에 원소 추가
push(value) {
this.data[this.length] = value;
this.length++;
}
// 배열의 맨 뒤 원소 제거
pop() {
const popValue = this.data[this.length - 1];
delete this.data[this.length - 1];
this.length--;
return popValue;
}
// 배열의 맨 앞 원소 추가
unshift(value) {
this.pushArray(0);
this.data[0] = value;
this.length++;
}
// 배열의 맨 앞 원소 제거
shift() {
const shiftValue = this.data[0];
delete this.data[0];
this.pullArray(0);
this.length--;
return shiftValue;
}
// 배열의 맨 앞과 뒤가 아닌 특정 위치에 원소 추가
insert(idx, value) {
this.pushArray(idx);
this.data[idx] = value;
this.length++;
}
// 배열의 맨 앞과 뒤가 아닌 특정 위치에 원소 제거
delete(idx) {
const deleteValue = this.data[idx];
delete this.data[idx];
this.pullArray(idx);
this.length--;
return deleteValue;
}
// 배열의 데이터를 뒤로 밀기
pushArray(idx) {
for (let i = this.length - 1; i >= idx; i--) {
this.data[i + 1] = this.data[i];
}
}
// 배열의 데이터를 앞으로 당기기
pullArray(idx) {
for (let i = idx; i < this.length; i++) {
this.data[i] = this.data[i + 1];
}
delete this.data[this.length - 1];
}
}
const myArray = new Array();
myArray.push(1);
console.log(myArray);
myArray.push(2);
console.log(myArray);
myArray.push(3);
console.log(myArray);
myArray.delete(1);
console.log(myArray);
myArray.pop();
console.log(myArray);
myArray.push(4);
console.log(myArray);
myArray.insert(1, 5);
console.log(myArray);
myArray.unshift(6);
console.log(myArray);
myArray.shift();
console.log(myArray);