단순 검색 대 이진 검색 알고리즘.

안녕 !
Big O Notation을 가장 간단한 단어로 설명하는 동안 환영하고 함께 있어 주세요!

"알고리즘을 실행하는 데 필요한 총 시간"은 Big O Notation의 가장 간단한 정의이지만 이것이 개발자에게 중요한 이유는 무엇입니까?

이에 답하기 위해 아래는 배열에서 주어진 항목을 찾는 간단한 검색 알고리즘입니다. 주어진 항목이 배열에 없으면 알고리즘이 null을 반환합니다.

단순 검색 알고리즘.

           Fig 1.0 (For-loop search algorithm )

위는 배열의 각 항목을 반복하고 현재 반복이 입력('item' )과 같은지 확인하고 항목이 배열에 없으면 "null"을 반환하는 간단한 JavaScript For-loop입니다.

아래(그림 2.0)는 위의 For-loop와 동일한 작업을 수행하는 while 루프입니다.

이진 검색 알고리즘.

      Fig 2.0 (while loop search algorithm )

그러나 위의 기능은 정확히 동일한 작업을 수행합니다. 하지만 배열의 항목 수가 기하급수적으로 증가하면 어떻게 될까요?

두 알고리즘 모두 얼마나 효율적일까요?

이진 검색 알고리즘의 단계별 분석:

배열의 중간 인덱스와 '항목'을 비교합니다.

'item'이 mid 인덱스와 일치하면 mid 요소를 반환합니다.

그렇지 않으면 'item'이 중간 요소보다 크면 배열의 길이가 중간( 요소 - 1 )에 재할당됩니다.

그렇지 않으면 'item'이 중간 요소보다 작으면 배열의 시작 부분이 중간 요소( 요소 + 1 )에 재할당됩니다.

이 방법을 사용하면 첫 번째 비교에서 어레이의 절반을 제거합니다.

더 나은 이해를 위해,
어레이의 길이가 1million으로 증가하는 경우.
첫 번째 기능(그림 1.0)으로 항목을 찾기 위해 100만 번의 반복(최악의 경우)을 수행합니다. 그러나 두 번째 함수로 최대 10번의 반복(최악의 경우)을 수행합니다.

함수의 Big O 표기법.

간단한 검색 알고리즘 (Fig 1.0) - O(n)//Bad guy
이진 검색 알고리즘(그림 2.0) - O(log n)//Good guy.

알고리즘과 데이터 구조를 가능한 한 간결하게 설명하는 동안 이 블로그에서 저와 함께 하세요.

코드에 연결하고 별표를 주는 것을 잊지 마십시오.
https://github.com/Olatisunkanmi/Data-Structures-and-Algorithms-/tree/main/5%20Algorithms/Binary%20Search