binary search, Big O

검색 속도는 정렬된 알고리즘에서 훨씬 빨라짐 (binary(둘로쪼개다) search 가능)

binary search에서 정렬의 중간부터 시작.  중간 숫자가 목표숫자보다 큰지 작은지 판별.

1~10에서 중간숫자는 5. 목표숫자가 9라면 5는 9보다 작으므로 5의 오른쪽부분만 신경쓴다.

6 7 8 9 10이 남음 중간숫자 8. 

8은 목표인 9보다 작다.

9와 10만 남김.

목표인 9가 10보다 작고 확인했음.

매 step 마다 절반이 됨.

item이 두배가 되어도 1회만 증가 

2^(n-1)과 2^n 사이의 숫자면 최악이어도 n step 까지만 

 

선형검색 한개씩 찾음.

1~10까지의 배열에서 10을 찾으려고 하면 최악의 경우에 맨뒤 index에 10이 있을 경우 열번 확인할 필요가 있을수도 있음.

Input size가 N이면 N steps 요구.

-> 시간복잡도 O(N) ->사이즈 N이면 N회 요구 

 

배열을 input으로 0번째 index를 출력하는 함수는 input이 몇이든 한번 실행으로 끝남.

input이 몇이든 동일 step 이면 constant time (상수 시간)

시간복잡도 O(1)

두번 실행하는 함수가 되더라도 O(2)가 아닌 O(1)

디테일한 부분이 아니라 큰 작동원리만 신경쓰는 표기법.(상수는 신경쓰지 않음)

 

배열의 모든 항목을 출력하는 함수가 된다면

input에 따라 동일한 step이 됨 (선형검색과같이)

O(N) (선형시간)

배열 모든항목 출력을 2회 반복하더라도

O(2N)이 아닌 O(N)인 것. (상수 신경 X)

input이 증가하면 step이 선형적으로 증가한다는 사실은 변하지 않았기 때문

우상향 일차함수 그래프

 

2차 시간

받은 배열을 2중 for문을 사용해서 n번 출력하게 하려면  

시간복잡도는 인풋의 n^2 O(N^2)

선형시간보다 비효율적.

 

로그 시간

이진검색을 할 때 절반씩 나눠서 검색했기에 input이 두배가 될때마다 step이 1 증가했음.

O(logN)

효율적

 

알고리즘의 속도는 완료까지 걸리는 절차의 수로 결정

 

참고

https://www.youtube.com/watch?v=BEVnxbxBqi8&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=4&t=90s