바이너리 검색이 순차 검색보다 어느 시점에서 효율적입니까?

Question

저는 최근에 알고리즘에 대해 많은 것을 배웠습니다. 검색된 바이너리는 의 많은 양의 항목을 찾기 위해 효율을 높이기 위해 데이터로 정렬되었습니다. 그러나 데이터가 정렬되지 않으면 어떻게 될까요? 어떤 지점에서 이진 검색은 순차 검색에 대한 효율성 향상을 제공하며 이진 검색은 먼저 해당 검색에서 지정된 배열을 정렬해야합니다. 필자는 바이너리 검색이 순차 검색을 통과하는 지점을보고 관심을 가지고 있습니다.

을 감안할 때 이진 검색가 필요하기 때문에 나는, ...의 말을 삼을 수 있도록, 순차적 종류가 주어진 번호를 찾을하는 것이 더 효율적이 될 것입니다 가정 것

1 3 6 3 1 87 56 -2 4 61 4 9 81 7 

14 개 요소

와 배열 foo는 [BUFF] 먼저 배열 정렬 수 3. 검색 BUT :

주어지지 천 개 요소 배열 바 [BUFF]

1 2 4 9 -2 3 8 9 4 12 4 56 //continued 

내가 이의가 없으면 이진 검색을 호출하는 것이 이론적으로 더 효율적이어야합니다.

Answer 1

정보가 알려지지 않은 정렬되지 않은 배열에서 선형 시간 검색을 수행해야합니다.

선형 시간 검색은 각 요소를 한 번 검사하므로 복잡도는 O(n)입니다. 정렬과 비교하기. 각 요소를 두 번 이상 확인해야하며 복잡도는 O(n * log n)입니다. 따라서 정렬을 수행하는 경우 순차 검색보다 속도가 느립니다. 이진 검색은 O(log n)이지만 임의로 데이터를 주문한 경우에는 쓸모가 없습니다.

물건을 여러 번 검색 할 경우 장기적으로 효율성이 높아 지므로 먼저 여러 항목을 정렬하는 것이 좋습니다.

Answer 2

여러 번 검색해야하는 경우 검색하기 전에 정렬하는 것이 더 빨라질 것입니다. 단일 요소 만 찾을 필요가 있다면 정렬은 느려질 것입니다. 정렬은 필연적으로 어떤 시점에서 모든 요소를 ​​반드시 검사해야하기 때문입니다.

여러 검색을 수행하는 경우 먼저 정렬 할 가치가있을 수 있지만 선형 검색과 사전 정렬 + 이진 검색 사이의 손익분기 점은 필요한 검색 수, 요소 수 , 사용 된 정렬 알고리즘 및 정렬되는 데이터.