시간복잡도 잘문

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

2개의 스택으로 1개의 큐를 구현하는과정에서

dequeue()를 할 때, 아웃스택이 비어있지않은 경우에는 O(1)을 갖고, 아웃스택이 비어있지 않은 경우에는 O(n)의 시간복잡도를 갖는건 이해했는데

왜 결론적으로 O(1)의 시간복잡도를 갖는지 모르겠습니다.

amortized의 정의도 함께 알려주시면 감사할것같습니다.

안녕하세요. .kyle3444님

amortized에 대해서는 자세히 설명하기에는 면접에서는 그렇게 중요하지 않아서 설명을 빼놓긴 했어요.

이 영상을 참고해보면 조금 이해가 되실 수 있을 거에요.

뒤쪽에 amortized에 대한 설명이 있습니다.

간단히 설명드리자면,

만약에 누군가 kyle님에게 하루에 돈 얼마써? 라고 물어봤다고 가정해볼게요.

364일동안 1만원을 쓰다가 하루정도는 100만원을 썼다고 해보면 다음과 같겠죠.

1만원 O(1)
1만원 O(1)
1만원 O(1)
100만원 O(n)
1만원 O(1)
1만원 O(1)
...
1만원 O(1)
1만원 O(1)
1만원 O(1)

평소에 항상 1만원을 쓰고 있는데, 가끔 100만원을 썼다고 해서 하루에 평균 100만원을 쓴다고 말하지 않습니다. 일년 전체로 봤을 때는 사실 평균 1만원정도 쓴다고 말하는게 맞겠죠.

근데 100만원 쓰는 날이 조금 많아져서, 일년동안 100일이나 100만원을 썼다고 해볼게요.

그러면 평균 1만원 쓴다고 말하기는 좀 그렇겠죠. 평균 100만원 O(n)에 가까운 돈을 쓰는게 맞을거에요.

그럼 이 경계가 애매하죠. 일년중 며칠이상 100만원 O(n) 썼을 때부터 평균O(n)이라고 말할 수 있을까?

그건 저희의 범위를 넘어서고 수학적인 계산이 많이 가미되기 때문에, 면접 질문에서도 물어볼 가능성이 높지 않아요.(면접질문 수백개중에서 amortized를 물어본적은 못보긴했습니다.)

그래서 그냥 대부분의 경우 O(1)이고 아주 가끔 O(n)이 발생하면 대강 amoritzed O(1)이라고 치자~ 하는거죠.

이정도로 이해해도 굉장히 충분할거에요 ㅎㅎ

그리고 kyle님께서 질문하신 내용은 O(1)으로 적혀있고, 첨부해주신 이미지 파일은 queue 두개를 이용하여 stack을 구현하는 문제입니다.

혹시 더 궁금하신 점 있으시면 언제든 질문해주세요 :)

인프런 커뮤니티 질문&답변