Big O / 시간복잡도 / Binary Search / Linear Search

 

선형 검색의 시간 복잡도는 

요만큼이야 라고 설명하기보다는 

O[N] 이다 라고 설명하는게 좋다. 

 

공통적으로 모든 사람이 이해 하고 내용이 명확하게 어느정도인지 공유되고 알 수 있음

 

 

O[N] 으로 쓰는 게 Big O 표기법이다.

 

 

 

상수 알고리즘 

어떻게 해도 배열만큼. 

 O(1) 라고 표기한다. 인풋의 크기가 얼마나 되는 지는 상관이 없다.

 

위와 같은 알고리즘이 상수 알고리즘 항상 이렇게 구현 할 수 있을리가 없다.

 

에 속한다.  보기도 쉽고 알기도 쉽다.

 

 

 

 

 

 

다음은 

 

 

O(N) 로 표기한다. 

 맨처음에 나타난 그래프가 O(N)이다 대각선 그래프다.

 

 

 

 

 

 

 

Quadratic Time ( 2차 시간 ) 

 

2차 시간은 Nested Loops (중첩반복) 이 있을 때 발생한다. 

 

 

 

배열의 각 아이템에 대해 루프를 반복해서 실행한다. 

 

 

따라서 시간복잡도는 인풋의 N^2 에 해당한다.

 

 

앞서 본 선형 시간보다는 이차시간의 속도가 더 느리겠지.

 

 

 

 

로그 시간(Logarithmic time) 

 

주로 이진 검색 알고리즘을 설명 할 때 쓴다. (binary search)

 

이진 검색에서는 인풋 사이즈가 2배가 되어도 거쳐야하는 step이 1만 증가하게 된다. 

 

 

라는 표현을 O(log N) 으로 할 수 있다. 

 

로그는 지수의 정 반대이다.

 

 

 

N = 5

32를 2로 몇번 나눠야 1이 나오는가?

 

그러니까 input이 2배 늘어도 1번만 더 나눠도 되니까 1만 증가한다.

 

 

상수보단 느리지만 2차 시간보단 빠르다.

 

하지만 이진 검색은 정렬되지 않은 배열에는 쓸 수없다. 

 

 

 

 

 

 

 

보통은 상수시간 - 로그 - 선형 - 지수시간 순으로 본다. 

 

무엇을 언제 선택해야 하는가를 고민해야 한다. 

 

 

 

 

 

 

 

본 김에 바이너리 서치  / 선형검색 (리니어) 까지 보자. 

 

 

Linear Search (선형검색 알고리즘)

 

 

 

 

처음부터 끝까지 찾는게 나올 때까지 반복한다. 

 

 

Linear Time Complexity = 선형 시간 복잡도. 

 

찾는 값이 없거나, 맨 마지막에 있다면.. 인풋의 값이 커질 수록 시간복잡도도 늘어나게 되는 문제가 있다. 

 

 

있어서 다행이지 없다면?

 

 

 

 

 

그래서 

 

Binary Search .  --> sorted array를 알아둬야한다. 

 

 

정렬된 상태에서 써야하지만 정렬된 상태에서 배열에 값을 추가하는 것은 정렬이 안된 경우보다 시간이 더 걸린다. 

( 중간값보다 큰 값을 찾고 중간에 값을 끼워 넣어야 하는 과정을  0번 인덱스부터 시작한다. )

 

 

하지만 정렬이 되었다면 검색에서는 시간이 빨라지게 된다. 

 

 

 

이진검색은 중간에서 부터 시작한다. 

 

 

정렬이 선행되어야 의미가 있다.

9를 찾는 데, 중간에서 시작한 값이 5라면 오른쪽 배열로 이동하면 된다. 

 

 

 

 

위에서 행한 작업을 오른쪽 배열에서 다시 반복한다. 

 

8이 9보다 작으니까 오른쪽배열을 찾는다. ( 반복 ) 

 

 

정렬 = 삽입은 느리지만 = 검색은 빨라지게 된다.

 

 

시간되면 문제 풀어 볼 것.