[이진 탐색 실전 문제] 원하는 정수 찾기 편 질문

Question

안녕하세요? 강의를 듣다가 궁금한 것이 생겨 질문 드립니다.

자바의 정렬 기본 알고리즘 시간 복잡도와 이진 탐색 시간 복잡도가 nlogn인 건 이해했는데, 코드부를 보면 이중 반복문이 나오고 있습니다.

앞 서 강의에서 반복문을 기준으로 이중 반복문이면 n의2승이라고 말씀하셨는데, 이 중 반복문을 썼는데도 nlogn이 되는 건 반복문이 진행되는 동안 절반씩 찾기 때문인가요??

만약 이중 반복문으로 시간 복잡도가 올라간다면 이중 반복문을 쓰지 않고, 해결하는 방법을 알려주실 수 있으실까요?

harucoding · Answer

개발주아님 안녕하세요. 반갑습니다. 이진탐색의 경우 제가 이해하기로는 만약 데이터가 정렬이 되어있는 상태라면 logn의 시간복잡도를 가지게 되고 미정렬 상태라면 정렬을 먼저 수행해야하기 때문에 일반적인 정렬 시간 복잡도인 nlogn이 더해지게 됩니다. 따라서 정렬하는데 걸리는 시간 (nlogn) + 이진 탐색 (logn) = nlogn (상수는 무시, 제일 오래 걸리는것 기준) 정도로 생각하면 되지 않을까 싶습니다. 질문 주신 내용으로 들어가보면 말씀하신 이중 반복문은 아마도 for(int i = 0; i< M; i++) while(start <= end ) 를 뜻하는 것으로 이해하였습니다. 실제 여기에서 이진 탐색을 수행하는 부분은 while 문으로 logn의 시간복잡도를 가지게 됩니다. (개발쥬아님이 말씀해주신데로 절반씩 찾기 떄문입니다.) for문의 경우 이진 탐색에 관련 된 부분이 아닌 문제의 요구사항으로 인하여 이진탐색을 수행하는 횟수로 생각하여 주시면 좋을 것 같습니다 (요구사항에 따라 해당 이중 반복문은 필수적으로 필요하다고 생각됩니다.) 즉 logn의 시간복잡도를 가지는 이진 탐색을 M번 수행하는 로직이다로 생각해주시면 되고 주어진 M의 범위가 N과 동일하기 때문에 결국 이 이중 포문의 시간 복잡도는 mlogn => nlogn 이 됩니다. 전체 코드의 시간 복잡도를 따지면 해당 로직에서 nlogn, 위쪽에서의 Array.sort(A) 부분에서 nlogn 이 측정되고 nlogn + nlogn => nlogn의 시간복잡도를 가지게 됩니다. n의 범위가 100,000이며 시간 제한이 2초, nlogn에 대입을 하게되면 2억(1억에 1초)보다 작은 수가 나오기 때문에 시간안에 결과 도출이 가능하게 됩니다. 답변이 되셨으면 좋겠습니다. 즐거운 주말 보내세요.