이진 검색 알고리즘을 사용하는 프로그램의 시간 복잡도는 얼마입니까?

이진 검색 알고리즘을 사용하는 프로그램의 시간 복잡도는 "로그 수준"입니다. 이진 검색은 매우 효율적인 검색 방법입니다. 알고리즘 복잡도는 while 루프의 수입니다. 시간 복잡도는 "O(h)=O(log2n)"으로 표현됩니다.

이 튜토리얼의 운영 환경: Windows 7 시스템, Dell G3 컴퓨터.

이진 검색 알고리즘을 사용하는 프로그램의 시간 복잡도는 "로그 수준"입니다.

관련 추천: "Programming Learning"

이진 검색은 이진 검색(Binary Search)이라고도 하는데, 보다 효율적인 검색 방법입니다. 그러나 이진 검색을 위해서는 선형 테이블이 순차적 저장 구조를 채택해야 하며 테이블의 요소는 키워드에 따라 순서대로 정렬되어야 합니다.

검색 과정:

먼저 테이블의 요소가 오름차순으로 배열되어 있다고 가정하고 테이블의 중간에 기록된 키워드와 검색 키워드를 비교하여 두 개가 같으면 검색에 성공합니다. ; 그렇지 않으면 중간 위치 레코드를 사용하여 테이블을 변경합니다. 앞과 뒤의 두 개의 하위 테이블로 구분됩니다. 가운데에 기록된 키워드가 검색 키워드보다 큰 경우 이전 하위 테이블을 검색합니다. 그렇지 않으면 후자의 하위 테이블이 추가로 검색됩니다. 조건에 맞는 레코드가 발견되어 검색이 성공할 때까지 또는 하위 테이블이 존재하지 않아 검색이 실패할 때까지 위 프로세스를 반복합니다.

알고리즘 복잡성:

이진 검색의 기본 아이디어는 n 요소를 대략 동일한 두 부분으로 나누고 x=a[n/2]인 경우 a[n/2]를 비교하는 것입니다. x가 발견되면 알고리즘이 종료됩니다.

시간 복잡도는 while 루프의 수입니다.

총 n개의 요소가 있습니다.

는 점차적으로 n, n/2, n/4,...n/2^k(다음에 연산할 나머지 요소 수)를 따릅니다. 여기서 k는 숫자입니다.

n/2^k가 반올림되었으므로 >=1

즉, n/2^k=1

인 경우 k=log2n을 얻을 수 있습니다(2를 밑으로 하는 n의 로그입니다).

그래서 시간 복잡도는 O(h)=O(log2n)

로 표현할 수 있습니다. 다음은 이진 검색 구현을 위한 의사 코드입니다.

BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max

반 검색 방법은 이진 검색 방법이라고도 하며 요소 간의 순서 관계를 최대한 활용합니다. 최악의 경우에는 분할 정복 전략을 사용한다. 이 경우 탐색 작업은 O(log n)에 완료될 수 있다. 기본 아이디어는 다음과 같습니다. (배열 요소가 오름차순으로 정렬되어 있다고 가정) n 요소를 대략 같은 수의 두 부분으로 나누고 a[n/2]를 가져와 x=인 경우 찾으려는 x와 비교합니다. a[n/ 2]이면 x가 발견되고 알고리즘이 종료됩니다. x

더 많은 관련 기사를 보려면 PHP 중국어 웹사이트를 방문하세요! !

위 내용은 이진 검색 알고리즘을 사용하는 프로그램의 시간 복잡도는 얼마입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!