배열의 삽입과 삭제에는 O(n)의 시간이 필요하다

May 12, 2025, 04:37 AM

…

배열에서 원소의 값을 덮어씌우거나, 맨 뒤에 값을 추가 혹은 삭제 하는 경우 O(1)의 시간이 걸린다.

arr = Array.new(5)
arr[0] = 17  # 1번 원소의 값 17로 덮어씌움 
arr[1] = 34  # 2번 원소의 값 34로 덮어씌움

# 맨 뒤에 데이터 추가
num_element = 2        # 데이터 총 개수
arr[num_element] = 51
num_element += 1

# 맨 뒤 데이터 삭제
num_element -= 1
arr[num_element] = nil

하지만 배열 중간에 데이터를 추가하거나, 중간에 위치해 있는 데이터를 삭제하는 경우 shift 작업이 필요하다. Shift는 의미 그대로 해당 위치 이후에 있는 모든 데이터를 한 칸씩 밀어주거나 당겨오는 것을 의미한다.

데이터 삽입 -> 데이터 삽입할 공간 필요 -> 한 칸씩 오른쪽으로 shift
데이터 삭제 -> 비어있는 공간을 매꿈 -> 한 칸씩 왼쪽으로 shift

arr = Array.new(5) # [nil, nil, nil, nil, nil]
arr[0] = 17
arr[1] = 51
arr[2] = 68        # [17, 51, 68, nil, nil]

########### arr[1]번 위치에 '34' 삽입
num_element = 3
insert_at = 1
value = 34

num_element.downto(insert_at) do |i|
	arr[i] = arr[i-1]
end

arr[insert_at] = value
num_element += 1

print arr # [17, 34, 51, 68, nil]

########## 1번 원소 삭제
arr[0] = nil
for i in (0..num_element-1) do
	arr[i] = arr[i+1]
end

arr[num_element] = nil
num_element -= 1

print arr # [34, 51, 68, nil, nil]

배열에 속해있는 원소의 개수 만큼 반복을 해야하기 때문에, 삽입과 삭제의 시간복잡도는 O(n)이 된다. 그렇기 때문에 삽입과 삭제 연산이 잦은 경우 O(1)의 시간으로 해당 연산이 가능한 자료구조를 선택하는 것이 바람직하다.

확장 🌱

삽입/삭제가 O(1)으로 가능한 자료구조는 뭐가 있을까
- 연결리스트 (250513050442), 해시테이블 (250514212107)
시간복잡도는 왜 중요한가 -> 250515204930
시간복잡도는 사용하는 언어에 따라 달라질 수 있을까
배열을 제외하고 shift 작업이 필요한 경우가 있을까
- 루비에는 shift함수가 있다 -> 250516052830
shift 대신 매번 새로운 배열을 할당한다면?
- 성능은 오히려 나빠진다. O(n)은 여전하고, 메모리 사용이 증가함 => 공간복잡도 상승

배열의 삽입과 삭제에는 O(n)의 시간이 필요하다

확장 🌱

관련 노트 📘