이진 검색 복잡성을 계산하는 방법

이진 검색 복잡성을 계산하는 방법

---

나는 이진 검색이 검색에 필요한 입력을 반으로 줄이므로 log (n) 알고리즘이라고 말하는 것을 들었습니다. 나는 수학 배경이 아니기 때문에 관련이 없습니다. 누군가 좀 더 자세히 설명 할 수 있습니까? 대수 시리즈와 관련이 있습니까?

---

여기서는 좀 더 수학적 방법으로 볼 수 있지만 실제로는 복잡하지 않습니다. 비공식적 인 것보다 IMO가 훨씬 명확합니다.

문제는 1이 될 때까지 N을 2로 몇 번 나눌 수 있습니까? 이것은 본질적으로 당신이 그것을 찾을 때까지 이진 검색 (요소의 절반)을 수행한다는 것입니다. 공식에서 이것은 다음과 같습니다.

1 = N / 2 ^x

2 ^x 곱하기 :

2 ^x = N

이제 로그 _2를 수행하십시오 .

log ₂ (2 ^x ) = log ₂ N
x * log ₂ (2) = log ₂ N
x * 1 = log ₂ N

즉, 모든 것이 나눌 때까지 N을 N 번 나눌 수 있습니다. 즉, 요소를 찾을 때까지 N 로그 ( "이진 검색 단계 수행")를 나누어야합니다.

---

이진 검색의 경우 T (N) = T (N / 2) + O (1) // 반복 관계

재귀 관계의 런타임 복잡도 계산을위한 마스터 정리 적용 : T (N) = aT (N / b) + f (N)

여기서 a = 1, b = 2 => log (a base b) = 1

또한 여기에 f (N) = n ^ c log ^ k (n) // k = 0 & c = log (기본 b)

따라서 T (N) = O (N ^ c log ^ (k + 1) N) = O (log (N))

출처 : http://en.wikipedia.org/wiki/Master_theorem

---

T (n) = T (n / 2) +1

T (n / 2) = T (n / 4) + 1 + 1

T (n) = T (n / 4) + 1 + 1이되도록 The (n / 2)의 값을 위에 넣으십시오. . . . T (n / 2 ^ k) + 1 + 1 + 1 ..... + 1

= T (2 ^ k / 2 ^ k) + 1 + 1 .... + 1 최대 k

= T (1) + k

우리가 2 ^ k = n을 취했듯이

K = 로그 n

따라서 시간 복잡도는 O (log n)입니다

---

검색 시간이 절반이 아니므로 log (n)가되지 않습니다. 대수적으로 줄어 듭니다. 이것에 대해 잠시 생각하십시오. 테이블에 128 개의 항목이 있고 값을 선형으로 검색해야하는 경우 값을 찾으려면 평균 약 64 개의 항목이 필요합니다. 그것은 n / 2 또는 선형 시간입니다. 이진 검색을 사용하면 반복 할 때마다 가능한 항목의 1/2을 제거하여 값을 찾기 위해 최대 7 번만 비교하면됩니다 (로그베이스 2128은 7 또는 2에서 7 제곱은 128입니다). 이진 검색의 힘.

---

이진 검색 알고리즘의 시간 복잡도는 O (log n) 클래스에 속합니다. 이것을 큰 O 표기법 이라고 합니다. 이것을 해석해야하는 방법은 입력 크기 n의 입력 세트가 주어질 때 함수를 실행하는 데 걸리는 시간의 점근 적 성장을 초과하지 않는 것 log n입니다.

이것은 진술 등을 증명할 수있는 공식적인 수학적 용어입니다. 매우 간단한 설명이 있습니다. n이 매우 커지면 log n 함수는 함수를 실행하는 데 걸리는 시간을 초과합니다. "입력 세트"의 크기 n은 목록의 길이 일뿐입니다.

간단히 말해서, 이진 검색이 O (log n)에있는 이유는 각 반복에서 입력 세트를 반으로 나누기 때문입니다. 반대 상황에서는 생각하기가 더 쉽습니다. x 반복에서 최대로 이진 검색 알고리즘이 얼마나 긴 목록을 조사 할 수 있습니까? 답은 2 ^ x입니다. 이것으로부터 우리는 반대로 이진 검색 알고리즘이 평균 길이 n의리스트에 대해 log2 n 반복을 필요로한다는 것을 반대로 알 수있다.

왜 O (log n)가 아니라 O (log2 n)이 아닌지, 간단히 다시 넣기 때문입니다.-큰 O 표기법 상수를 사용하면 계산되지 않습니다.

---

Log2 (n)은 이진 검색에서 무언가를 찾는 데 필요한 최대 검색 수입니다. 평균 사례는 log2 (n) -1 검색과 관련이 있습니다. 자세한 정보는 다음과 같습니다.

http://en.wikipedia.org/wiki/Binary_search#Performance

---

다음은 위키 백과 항목

간단한 반복 접근법을 살펴보십시오. 필요한 요소를 찾을 때까지 검색 할 요소의 절반 만 제거하면됩니다.

다음은 수식을 작성하는 방법에 대한 설명입니다.

Say initially you have N number of elements and then what you do is ⌊N/2⌋ as a first attempt. Where N is sum of lower bound and upper bound. The first time value of N would be equal to (L + H), where L is the first index (0) and H is the last index of the list you are searching for. If you are lucky, the element you try to find will be in the middle [eg. You are searching for 18 in the list {16, 17, 18, 19, 20} then you calculate ⌊(0+4)/2⌋ = 2 where 0 is lower bound (L - index of the first element of the array) and 4 is the higher bound (H - index of the last element of the array). In the above case L = 0 and H = 4. Now 2 is the index of the element 18 that you are searching found. Bingo! You found it.

If the case was a different array{15,16,17,18,19} but you were still searching for 18 then you would not be lucky and you would be doing first N/2 (which is ⌊(0+4)/2⌋ = 2 and then realize element 17 at the index 2 is not the number you are looking for. Now you know that you don’t have to look for at least half of the array in your next attempt to search iterative manner. Your effort of searching is halved. So basically, you do not search half the list of elements that you searched previously, every time you try to find the element that you were not able to find in your previous attempt.

So the worst case would be

[N]/2 + [(N/2)]/2 + [((N/2)/2)]/2.....
i.e:
N/2¹ + N/2² + N/2³ +..... + N/2^x …..

until …you have finished searching, where in the element you are trying to find is at the ends of the list.

That shows the worst case is when you reach N/2^x where x is such that 2^x = N

In other cases N/2^x where x is such that 2^x < N Minimum value of x can be 1, which is the best case.

Now since mathematically worst case is when the value of
2^x = N
=> log₂(2^x) = log₂(N)
=> x * log₂(2) = log₂(N)
=> x * 1 = log₂(N)
=> More formally ⌊log₂(N)+1⌋

---

A binary search works by dividing the problem in half repeatedly, something like this (details omitted):

Example looking for 3 in [4,1,3,8,5]

1. Order your list of items [1,3,4,5,8]
2. Look at the middle item (4),
   • If it is what you are looking for, stop
   • If it is greater, look at the first half
   • If it is less, look at the second half
3. Repeat step 2 with the new list [1, 3], find 3 and stop

It is a bi-nary search when you divide the problem in 2.

The search only requires log2(n) steps to find the correct value.

I would recommend Introduction to Algorithms if you want to learn about algorithmic complexity.

---

Since we cut down a list in to half every time therefore we just need to know in how many steps we get 1 as we go on dividing a list by two. In the under given calculation x denotes the numbers of time we divide a list until we get one element(In Worst Case).

1 = N/2x

2x = N

Taking log2

log2(2x) = log2(N)

x*log2(2) = log2(N)

x = log2(N)

---

T(N) = T(N/2) + 1

T(N) = T(N/2) + 1 = (T(N/4) + 1)+ 1

...

T(N) = T(N/N) + (1 + 1 + 1 +... + 1) = 1 + logN (base 2 log) = 1 + logN

So the time complexity of binary search is O(logN)

---

ok see this
for(i=0;i<n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.

2. at each iteration n is divided by half.

2.a n=n/2                   .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)

So at i=k , n=1 which is obtain by dividing n  2^k times
n=2^k
1=n/2^k 
k=log(N)  //base 2

---

Let me make it easy for all of you with an example.

For simplicity purpose, let's assume there are 32 elements in an array in the sorted order out of which we are searching for an element using binary search.

1 2 3 4 5 6 ... 32

Assume we are searching for 32. after the first iteration, we will be left with

17 18 19 20 .... 32

after the second iteration, we will be left with

25 26 27 28 .... 32

after the third iteration, we will be left with

29 30 31 32

after the fourth iteration, we will be left with

31 32

In the fifth iteration, we will find the value 32.

So, If we convert this into a mathematical equation, we will get

(32 X (1/2⁵)) = 1

=> n X (2^-k) = 1

=> (2^k) = n

=> k log₂2 = log₂n

=> k = log₂n

Hence the proof.

---

Let say the iteration in Binary Search terminates after k iterations. At each iteration, the array is divided by half. So let’s say the length of the array at any iteration is n At Iteration 1,

Length of array = n

At Iteration 2,

Length of array = n⁄2

At Iteration 3,

Length of array = (n⁄2)⁄2 = n⁄22

Therefore, after Iteration k,

Length of array = n⁄2k

Also, we know that after After k divisions, the length of the array becomes 1 Therefore

Length of array = n⁄2k = 1
=> n = 2k

Applying log function on both sides:

=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)
As (loga (a) = 1)

Therefore,

As (loga (a) = 1)
k = log2 (n)

Hence the time complexzity of Binary Search is

log2 (n)

참고URL : https://stackoverflow.com/questions/8185079/how-to-calculate-binary-search-complexity