시간 복잡도 ~의 이진 검색 ~이다 O(로그 n) , 어디 N 배열의 요소 수입니다. 각 단계에서 배열을 절반으로 나눕니다. 공간 복잡도 ~이다 오(1) 일정한 양의 추가 공간을 사용하기 때문입니다.

문자열 자바 반전

이진 검색 알고리즘의 예

이진 검색 알고리즘의 시간 및 공간 복잡성은 아래에 언급되어 있습니다.

시간 복잡도 이진 검색 알고리즘 :

이진 검색 알고리즘의 최상의 경우 시간 복잡도: 오(1)

가장 좋은 경우는 요소가 배열의 중간 인덱스에 있는 경우입니다. 대상 요소를 찾는 데는 한 번의 비교만 필요합니다. 따라서 가장 좋은 경우의 복잡성은 다음과 같습니다. 오(1) .

이진 검색 알고리즘의 평균 사례 시간 복잡성: 오(로그 N)

배열을 고려하세요 도착[] 길이의 N 및 요소 엑스 찾을 수 있습니다. 두 가지 경우가 있을 수 있습니다:

• 사례 1: 요소가 배열에 존재합니다.
• 사례2: 요소가 배열에 없습니다.

있다 N Case1 및 1 사례2. 따라서 총 경우의 수 = N+1 . 이제 다음을 확인하세요.

• 인덱스 N/2의 요소는 다음에서 찾을 수 있습니다. 1 비교
• 인덱스 N/4 및 3N/4의 요소는 다음에서 찾을 수 있습니다. 2 비교.
• 인덱스 N/8, 3N/8, 5N/8 및 7N/8의 요소는 다음에서 찾을 수 있습니다. 삼 비교 등등.

이를 바탕으로 다음이 필요한 요소라는 결론을 내릴 수 있습니다.

부분 파생 기호 라텍스

• 비교 1개 = 1
• 2개의 비교 = 2
• 3개의 비교 = 4
• 엑스 비교 = 2 ^x-1 어디 엑스 범위에 속한다 [1, 로그N] 최대 비교 = N을 절반으로 줄일 수 있는 최대 시간 = 첫 번째 요소에 도달하기 위한 최대 비교 = logN.

그럼 전체적인 비교는
= 1*(1번의 비교가 필요한 요소) + 2*(2번의 비교가 필요한 요소) + . . . + logN*(logN 비교가 필요한 요소)
= 1*1 + 2*2 + 3*4 + . . . + 로그N * (2^로그N-1)
= 2^침착한* (logN – 1) + 1
= N * (logN – 1) + 1

총 건수 = N+1 .

따라서 평균 복잡성 = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . 여기서 주요 항은 N*logN/(N+1)이며 이는 대략 다음과 같습니다. 침착한 . 따라서 평균 사례 복잡성은 다음과 같습니다. 오(로그N)

다이애나 메리 블랙커

이진 검색 알고리즘의 최악의 경우 시간 복잡도: 오(로그 N)

최악의 경우는 요소가 첫 번째 위치에 있을 때입니다. 평균적인 경우에서 볼 수 있듯이 첫 번째 요소에 도달하는 데 필요한 비교는 다음과 같습니다. 침착한 . 따라서 최악의 경우의 시간복잡도는 다음과 같습니다. 오(로그N) .

이진 검색 알고리즘의 보조 공간 복잡성

그만큼 보조 공간 복잡도 ~의 이진 검색 알고리즘 ~이다 오(1) 이는 입력 배열의 크기에 관계없이 일정한 양의 추가 공간이 필요함을 의미합니다. 이는 이진 검색이 입력 크기에 따라 증가하는 추가 데이터 구조나 재귀가 필요하지 않은 반복 알고리즘이기 때문입니다. 그러나 이진 검색을 재귀적으로 구현할 수도 있습니다.