4-B 시간복잡도

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 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}}   '||'로 집합을 구분했습니다 제가 놓친 부분이 있을까요?

큰돌 · Answer

안녕하세요 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점은 제게 큰 힘이 됩니다. 감사합니다.