Search
Duplicate
🎈

binary search 시간 복잡도 수학적 증명

태그
Algorithm
Math
Proof
공개여부
작성일자
2021/11/03
Binary Search 는 왜 log(n)log(n) 으로 시간 복잡도를 설명할까? 시간, 공간 복잡도는 이전에도 다뤄본적이 있지만, 수학적으로 증명할 필요가 있다 여겨 살펴보게 되었다.
이전에 작성했던 글은 Recursive 인데 Big O table 이 포함되어 있다
참조한 대표적인 contents 는 youtube와 geeksforgeek 이다
binary search 의 선제 조건은 입력받은 배열이 sorting 되어 있다는 점이다.
fun binarySearch(arr: Array<Int>, findValue: Int, start: Int, end: Int): Int { val middleIndex = (start + end) shr 1 return if (arr[middleIndex] == findValue) { arr[middleIndex] } else if (start == end) { -1 } else if (arr[middleIndex] > findValue) { binarySearch(arr, findValue, start, middleIndex - 1) } else { binarySearch(arr, findValue, middleIndex + 1, end) } }
Kotlin
이러한 binary search 함수를 만들었다 recursive 로 구현하였고 우리가 아는 binary search 알고리즘이다
주어진 배열은 다음과 같다
[3, 6, 9, 13, 17, 24, 39, 57, 73, 92]
Kotlin
여기서 우리가 할 일은 24를 찾는 것이다.

Iteration 1

arr: [3, 6, 9, 13, 17, 24, 39, 57, 73, 92]
middleIndex 를 찾아낸다 여기서는 4가 된다
index 4의 value 는 24 이다.
길이는 10이다

Iteration 2

arr: [24, 39, 57, 73, 92]
middleIndex: 7
value: 57
length: 5

Iteration 3

arr: [24, 39]
middleIndex: 0
value: 24
length: 2
MATCHED!

24를 찾을 경우의 수

Iteration 1

array=narray = n

Iteration 2

length=n/2length = n/2

Iteration3

length=(n/2)(1/2)=n/22length = (n/2)*(1/2) = n / 2^2
따라서 k 번 iteration을 해야한다면 다음과 같은 수식으로 귀결된다
length=n/2k=>n=2klength = n / 2^k => n = 2^k
kk 를 구하기 위해서 다음과 같이 정의할 수 있다
n=2k=>log2(n)=log2(2k)n = 2^k => log_2(n) = log_2(2^k)
loga(a)=1log_a(a) = 1 이므로 k는 다음과 같다
k=log2(n)k = log_2(n)
lim(log2(n))=1lim(log_2(n)) = 1
계차수열의 합 공식인줄 알았는데, 그냥 공비수열이었음.....
수열간의 관계
TOP