-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
[코테 적용] LIFO 2번째 문제 시간복잡도 질문
23.02.16 00:43 작성 23.02.16 00:46 수정 조회수 302
2
안녕하세요 좋은 강의 감사합니다 !!
바로 본론으로 들어가면, 여기서 조건이 10^5 이니깐 O(n^2) 로 풀면 안된다고 하셨는데..
for 문 안에 while 문이 있으니깐 결국 O(n^2) 아닌가요??
temperatures 도 한번 훑고, stack 도 한번 훑으니깐 총 O(n^2) 이라고 생각했는데 잘못 이해하고 있나봐요 ㅜㅜ
시간복잡도 질문 - 밤의멜로디 님이 주신 질문에 대한 답변 내용이라면 while 문도 O(n^2) 이 아닌가 라는 생각이 듭니다..
답변을 작성해보세요.
2
밤의멜로디
2023.02.17
이거는 제가 남긴 거랑 조금 다른거 같긴한데,
가장 마지막에 담긴 온도가 지금 온도 보다 작을때만 동작 하는거라서 이 경우에는 while문이 굉장히 적게 돌아요. 경우에 따라서는 while문이 아예 안 돌 수도 있구요.
최악의 경우(모든 온도가 첫번째보다 낮아지다가 맨 마지막에 온도가 높은경우)에 n번을 돌긴 할텐데
그렇게 되면 결국 O(2n)이라서 O(n)이 되긴 해요.
제가 질문했던 거는 반복문이 무조건 돌아야 했었던거라....
제 생각이 틀릴수도 있는데, 각자 생각을 공유하다 보면 서로한테 도움이 되지 않을까 해서 남겨 봅니다 ㅎㅎ
밤의멜로디
2023.02.17
아 이거는 그냥 제 개인적인 의견이라 틀릴수도 있으니 참고 정도로만 부탁드립니다 ㅎㅎ
최악의 경우 O(2n)이 된다는 거는 while문이 돌 때 최대 많이 돌 수 있는 수가 얼마인지를 최악의 경우로 봤는데, 이 경우는 반드시 마지막까지 더 따뜻한 날이 온다는 전제 하에요.
반드시 더 따뜻한 날이 온다면 스택에 있는 모든 정보를 다 빼야 되기 때문에 반드시 n번을 돌아야 하거든요.
결국 while문이 돌 수 있는 가장 많은 수는 아무리 많아 봐야 n번이라는 거죠.
따로 나눠서 돌든 한번에 돌든 최악의 경우 n 번이 돌아가는 거고 운 좋아서 첫번째 날씨 보다 두번째 날씨만 좋고 나머지 날씨는 점점 떨어진다면 while문은 딱 한번만 돌겠죠.
그렇기 때문에 최악의 경우라도 반복문의 합은 n 번이기 때문에 O(2n) = O(n)이 되는거죠.
바꿔 말하자면 stack에 들어갈 수 있는 개수는 최대 n개이고 stack에서 빼 봤자 n개 밖에 뺄 수 없으니까 나눠서 돌든 한번에 돌든 n번의 반복문 밖에 돌아갈 수 없다는 뜻이죠.
글로 적다보니 잘 전달이 안 될 수도 있는데 이해하시는데 조금이라도 도움이 됐으면 합니다.
물론 제 생각일 뿐, 틀릴수도 있습니다!
별이
2023.02.17
@밤의멜로디 님 자세한 설명 정말 감사합니다 ^^!! 덕분에 이해가 많이 되었어요!!! 강의를 계속 듣다보니 이에 대한 내용이 나오네요! 혹시 다른 궁금한 분들을 위해 남겨 놓을게요. < 강의 Hash Table - [코테 적용] [2] Key in (전반부) 20:12부터 >
0
답변 2