시간복잡도

Question

Q. Stack 두 개를 이용하여 Queue를 구현해 보세요. 강의의 꼬꼬무 문답으로 Q. 시간복잡도는 어떻게 되는지 설명해 주세요. 관련 질문입니다. dequeue() : 두 가지 경우를 따져봐야 합니다. worst case는 outstack이 비어있는 경우입니다. 이 때는 instack에 있는 n개의 데이터를 instack.pop()을 한 이후에 outstack.push()를 해줘야 합니다. 따라서 총 2*n 번의 operation이 실행되어야 하므로 O(n)의 시간복잡도를 갖습니다. 하지만 outstack이 비어있지 않는 경우에는 outstack.pop()만 해주면 됩니다. 이는 O(1)의 시간복잡도를 갖습니다. 이를 종합했을 때, amortized O(1)의 시간복잡도를 갖는다고 할 수 있습니다.   전반적으로 이해가 가지만 ' 이를 종합했을 때, amortized O(1)의 시간복잡도를 갖는다고 할 수 있습니다. ' 이 부분이 헷갈립니다.   outstack의 비어있을지 아니면 데이터가 있을지는 모르는 건데, 왜 amortized O(1)의 시간복잡도를 갖게 된 것 일까요?

nossi · Answer

맞습니다 outstack이 비어있을지 데이터가 있을 지 모르는상황입니다. 그래서 각각의 상황에 따라서 시각복잡도를 구한게 다음과 같은 상황입니다. dequeue()의 시간복잡도: 비어있을 때 worst case => O(n) 비어있지 않을 때 best case => O(1)   여기까지는 저희가 서로 동의한 상황인데, 문제는 모든 operation에 대해서 상황을 나눠서 "worst case때에는 시간복잡도가 이거고, best case일때에는 시간복잡도가 저거야" 라고 말하기는 좀 번거롭죠!   "아니 그래서 평균적으로 시간복잡도가 뭐야 하나만 말해줘!" 라는 요청에 보통 평균 복잡도를 말하죠. 문제는 평균복잡도는 구하기 너무 어렵다는 겁니다. 여러 방법이 있지만, 보통 worst case와 average case는 시간복잡도가 같은경우가 많고, 상한을 말해야 최악의 상황에서도 사용할 수 있는 알고리즘을 작성할 수 있기 때문에 average case 를 worst case로 말하는 경우가 많습니다.   하지만 우리가 작성한 dequeue()의 경우에는 n번 dequeue()를 한다면 worst case의 시간복잡도는 딱 한번 발생한다고 볼 수 있습니다. 이처럼 너무 가끔 worst case가 발생한다면 분할상환 (amortized) 시간복잡도로 계산을 하여 평균 시간복잡도를 구하죠   예를들어 한달에 한번 300만원짜리(O(n)) 물건을 구매했지만, 나는 한달에 평균적으로 10만원 쓰는 사람(amortized O(1))이라고 칭하는 것 과 비슷해요. 말 그대로 분할상환이죠!   혹시 이해에 도움이 되실까 해서 그림을 간단히 그려봤습니다.   혹시 도움이 되셨을까요!!?