인프런 커뮤니티 질문&답변
작성한 질문수
시간복잡도 질문
해결된 질문
23.02.14 21:26 작성
·
407
2
안녕하세요 강사님
알찬 강의 구성으로 재미있게 강의를 듣고 있습니다.
다름이 아니라 시간 복잡도에 대해서 여쭤보고 싶은게 있어서 글을 남깁니다.
현재 완전탐색을 하게 되면 시간 복잡도가 n2이 된다고 하셨는데, 두번째 반복문 조건을 j = i+1 로 설정하는 순간부터 n2이 아니라 n log n이 되는 것이 아닌가 싶어서요.
만약 nums의 길이가 5라면 최악의 경우에도 반복문이 전체가 돌아간다면 ( 4+ 3+ 2+ 1 ) = 10번으로 n2 = 25일때보다는 획기적으로 줄어드는 것 같아요!
5의 경우에도 절반 이하로 줄어들었는데 숫자가 커지면 커질수록 기하급수적으로 줄어들 것으로 보이는데, 혹시 제가 잘못 생각하고 있는 걸까요? ㅠㅠ
답변 1
2
2023. 02. 14. 23:44
안녕하세요 밤의 멜로디님.
이게 수학적인 내용도 있어서 좀 더 제가 자세히 설명드렸어야 됐는데, 그러지 못한 것 같아서 죄송스럽네요. 시간복잡도는 추후에 따로 섹션을 추가해볼게요.
말씀하신대로 nums의 길이가 5라면 최악의 경우에 4 + 3 + 2 + 1 이죠!
길이가 n이라면 최악의 경우 n-1 + n-2 + ... + 2 + 1이 됩니다. 이걸 다 더해보면 (n-1)(n)/2 가 나옵니다. (등차수열의 합)
맞는지 확인해볼까요? n = 5라면 (5-1)(5)/2 = 10 이 나오네요!
(n-1)(n)/2 = (n^2 - n) * 1/2 네요.
시간복잡도 빅오 노테이션으로 구해보면 O(1/2 * n^2 - 1/2 * n) 이렇게 나오는데 결국 O(n^2)이랑 같게 됩니다.
기하급수적으로 줄어들진 않고, n^2보단 반절? 반절정도 작긴 하겠네요. 그치만 그정도로는 크게 차이가 없습니다.
혹시 이해가 되셨을까요? 조금은 복잡할 수 있는 내용이라 ㅜ 이해가 잘 가지 않으시다면 말씀해주세요!!!
화이팅입니다
2023. 02. 15. 00:51
음... 등차수열을 수식으로 보니까 빅오 표기법 n^2이 되는게 이해가 되네요 ㅎㅎ
저는 좀 단순하게 생각해서 대략 n^2보다는 반정도 줄어드니까 n^(1*1/2) = n^3/2 정도로
생각해서 10^4가 입력값 제한이라고 가정하면 n^2을 사용했을 때는 10^8이 넘어가서 사용하면 안 되지만 위의 계산대로 n^3/2가 시간 복잡도가 된다면 10^6이 되니까 사용해도 되지 않을까 하는게 그냥 제 생각이었거든요 ㅎㅎ
친절한 답변 감사드립니다!