알고리즘의 시간 복잡성을 설명하십시오.

Question

while(low <= high) 
{ 
    mid = (low + high)/2; 
    if (target < list[mid]) 
    high = mid - 1; 
    else if (target > list[mid]) 
    low = mid + 1; 
    else break; 
} 

물론 이진 검색이지만 복잡성을 발견하고 싶습니다.

코드를 보는 것만으로 Big-O를 어떻게 찾을 수 있습니까?

while 루프의 경우 평균 N/2 번 실행됩니까?

그러나 바이너리 검색을 모르는 경우 코드를보고이 코드의 Big-O를 어떻게 찾을 수 있습니까?

Answer 1

당신은 단지 while() 조건 변경 ...

low <= high

가 어떻게 high - low 행동하라 볼 필요가 의미하는 방법을 참조 할 필요가있다.

코드에서 무엇이 가장 바뀌지 않는지 찾아보십시오! (최악의 경우)
여기 가 2 배만큼 감소된다 (반으로 낮은 사전에 하나 또는 그 반대로)을

:
T = 1 (< X = 0);
T (N) = T (N/2)

Answer 2

Big-O 표기법은 최악의 경우의 복잡도와 관련이 있으므로이 코드의 최악의 시나리오를 처리하면됩니다. break 회선에 도달하지 않습니다.

다른 if 분기는 while 루프의 각 반복 후에 high에 low으로부터의 거리가 약 절반으로 감소되는 것을 의미한다.

가정하자 N=|high-low|

처음 후 D 결국 이렇게 비가 N/(2^n) 때 high < low 및 while 루프 마감 있다고 0 같다고 N/2, N/4는 ... 2^n 반면 N/(2^n)보다 크거나 d과 동일해질 것이다.

그럼 우리는 얼마나 많은 시간을 2로 나눌 수 있습니까? N? 답은 대략 2 진수의 N의 로그이므로, log(N)의 복잡도입니다.