| [ QuizWit ] in KIDS 글 쓴 이(By): ash (물푸레나무) 날 짜 (Date): 2007년 12월 6일 목요일 오후 03시 45분 17초 제 목(Title): Re: [Q] 이상한 범위 찾기 > > 1 <= m <= n <= N 인 m, n이 있어서, m <= x <= n 에서 a[x]=1, 그 외에 > > a[x]=0 입니다. > > 우선 전체의 1/2을 검사. > 그 다음엔 1/4, 3/4을 검사. > 그 다음엔 1/8, 3/8, 5/8, 7/8을 검사. > 그 다음엔 1/16, 3/16, ... 16/16을 검사.. > > 이렇게 해서 a[k]=1인 k 값 하나를 찾는다. > -> 예상 시간: N/(n-m) 저는 이부분은 이렇게 생각했습니다. > 이렇게 하면 1 <= m <= k에서 m을 binary search, > k <= n <= N 에서 n을 binary search. > -> 예상 시간 2 log N k값을 찾은 전 단계에서 검사한 부분이 k의 앞 뒤로 있으므로 그부분 까지만 binary search하면 되니까 검사의 i 단계에서 k를 찾았다고 가정하면 -> 예상 시간 2 log (N/2^i) 그런데 i ~= log (N/(n-m)) 이므로 --> 2 log (n-m) ======= Murphy was an optimist. |