algorithm/common
deque는 어떻게 빠른가
아르르르를를르
2022. 6. 15. 19:08
알고리즘 문제를 풀다보면 흔히 list보다 deque(double ended queue)
가 훨씬 빠르다고 한다.
deque의 popleft()는 배열의 첫번째 데이터를 꺼내는 것으로 O(1)의 시간복잡도가 걸린다.
그 이유가 무엇인지 궁금하여 찾아보았다.
deque는 원형 큐
를 확장하여 손쉽게 구현할 수 있다. 다음과 같이 초기화 가능하다.
class Deque:
rear = 0
front = 0
MAX_SIZE = 100
deq = list()
def __init__(self):
self.rear = 0
self.front = 0
self.deq = [0 for i in range(self.MAXSIZE)]
이렇게 rear, front 변수를 활용하여 linkedlist와 비슷한 방식으로 삽입, 삭제시에 포인터 조정이 일어난다.
그래서 deque.popleft() 는 front += 1 형태의 연산만 수행하므로 O(1)의 시간복잡도가 가능한 것이다.
list.pop() 과 deque.pop()의 경우
맨 뒤의 값을 제거하는 것으로 수행시간에 큰 차이가 없어 stack으로 사용할 때는 list나 deque나 성능이 같다.
다만, queue가 필요할 때에는 deque로 개발하면 되겠다.
참고: https://codingsmu.tistory.com/124