인프런 커뮤니티 질문&답변
작성한 질문수
4-B 시간복잡도
작성
·
221
·
수정됨
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요, 선생님. 시간복잡도가 2^40 (20 짝+ 20 홀)이라 하였는데 어떻게 시간복잡도가 이렇게 나왔는지 궁금합니다.
만일 n=2 라하면 시간복잡도는 2^4 = 16개의 경우인데 실제 계산해보면 8개가 나오더군요.
입력값이 {{H,H},{H,H} 라하면, 4개의 원소 중 H또는 T가 단독으로 나오는 경우가 없기에 ( 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하니)
아래와 같이 모든 경우의 수(8)를 구했습니다.
{{H,H},{H,H}} || {{H,H}, {T,T}} || {{H,T}, {T,H}} || {{T,T}, {H,H}} || {{T,H}, {H,T}} || {{T,H}, {T,H}} || {{H,T}, {H,T}} || {{T,T}, {T,T}}
'||'로 집합을 구분했습니다
제가 놓친 부분이 있을까요?
답변 1
0
안녕하세요 01님 ㅎㅎ
안녕하세요, 선생님. 시간복잡도가 2^40 (20 짝+ 20 홀)이라 하였는데 어떻게 시간복잡도가 이렇게 나왔는지 궁금합니다.
>> 가로줄 20개, 세로줄 20개를 뒤집는 경우의 수를 합하면 2^40이 됩니다.
만일 n=2 라하면 시간복잡도는 2^4 = 16개의 경우인데 실제 계산해보면 8개가 나오더군요.
입력값이 {{H,H},{H,H} 라하면, 4개의 원소 중 H또는 T가 단독으로 나오는 경우가 없기에 ( 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하니)
아래와 같이 모든 경우의 수(8)를 구했습니다.
>> 네 결과의 경우의 수는 8개일지 몰라도, 우리는 로직의 시간복잡도를 계산하는 것이며 여기서 로직이란 뒤집는 것입니다. 뒤집는 행위에 대해서 시간복잡도를 최대치로 계산해보면 단순하게 세로줄 뒤집는다? 안뒤집는다. 등을 기반으로 판단하면 2^40이 되게 됩니다.
또 질문 있으시면 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다.
감사합니다.