🗒 본 내용은 [Hello Coding 알고리즘] 책을 공부하며 정리한 게시글입니다!
📌 알고리즘?
: 알고리즘은 어떤 일을 하기 위한 명령의 집합이다.
📌 이진 탐색(binary search)
: 이진 탐색은 알고리즘임. 입력으로 '정렬된 원소 리스트'를 받음.
리스트에 원하는 원소가 있으면 그 원소의 위치를 반환하고, 아니면 null 값을 반환함.
👉 이진 탐색은 로그 시간(logarithmic time)으로 실행됨
이진 탐색은 리스트의 원소들이 정렬되어 있어야만 사용 가능
정렬되어 있지 않다면?
📌 단순 탐색(simple search)
: 답에 도달할 때까지 하나하나 추측해보는 것.
예) 1~100 중에 생각한 숫자가 무엇인지 찾아내야 할 때, 답이 99라면 답에 도달하기까지 99번 추측해야 함.
👉 '이진 탐색'을 사용하면 단계마다 절반의 숫자를 제거할 수 있기 때문에 정답을 빠르게 맞출 수 있다.
📌 빅오 표기법(Big O notation)
: 빅오 표기법은 알고리즘이 얼마나 빠른지 표시하는 특별한 방법.
빅오 표기법은 속도를 시간 단위로 세지 않음(*연산 횟수를 비교하기 위한 것)
빅오 표기법을 사용하면 수행해야 할 일이 많아질 때 알고리즘에 걸리는 시간이 어떤 식으로 증가하는지를 알 수 있음
| 표기법 |
O(n)
= 알고리즘이 동작하기 위해 필요한 연산 횟수를 나타냄(*n = 연산 횟수)
가장 많이 사용하는 5가지 빅오 실행 시간
1. O(log n),로그 시간: 예) 이진 탐색
2. O(n), 선형 시간: 예) 단순 탐색
3. O(n*log n): 예) 퀵 정렬과 같이 빠른 정렬 알고리즘
4. O(n²): 예) 선택 정렬과 같이 느린 정렬 알고리즘
5. O(n!): 예) 정말 느린 알고리즘
📌 정리
- 이진 탐색은 단순 탐색보다 아주 빠름
- 알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는 지로 측정함
- 이는 입력 데이터의 크기가 늘어날 때 알고리즘의 실행 속도가 얼마나 증가하는지 알 수 있음
- 알고리즘의 실행 시간은 빅오 표기법으로 나타냄
- O(log n)는 O(n)보다 빠르고, 찾으려는 리스트의 원소의 개수가 증가하면 상대적으로 더 빨라짐
📚 Reference
: [book] Hello Coding 알고리즘
