점근표기법이란?
- 알고리즘의 성능을 수학적으로 표기하는 방법
- 알고리즘의 “효율성”을 평가하는 방법
- 빅오(Big-O) 표기법 - 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지
- 빅 오메가(Big-Ω) 표기법 - 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지
배열에서 특정 요소 찾기
길이가 6인 1차원 배열에서 '3'을 찾는 알고리즘의 시간 복잡도를 O(N)입니다.
case 1의 경우, 첫번째 원소에서 '3'을 찾을 수 있습니다.
case 2의 경우, 마지막 원소에서 '3'을 찾을 수 있습니다.
운이 좋지 않으면 input의 길이(N) 만큼 연산 이후에 답을 찾을 수 있습니다.
array = [3, 5, 6, 1, 2, 4] # 길이(N)이 6인 배열 - case 1
array = [5, 6, 1, 2, 4, 3] # 길이(N)이 6인 배열 - case 2
def is_number_exist(number, array):
for element in array: # array 의 길이만큼 아래 연산이 실행
if number == element: # 비교 연산 1번 실행
return True
return False
is_number_exist(3, array):
입력값에 따라 달라지는 연산량이 달라집니다.
- 빅오 표기법(최악) - O(N)
- 빅오메가 표기법(최상) - Ω(1)
- 알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석
- 입력값이 최선의 경우일 가능성은 굉장히 적고, 최악의 경우를 대비해야 하기 때문입니다.
입력 | 소요되는 연산량 |
좋을 때 | 1 |
좋지 않을 때 | N |
'알고리즘 > 이론' 카테고리의 다른 글
[알고리즘] 삽입 정렬 (Insertion Sort) (0) | 2022.04.28 |
---|---|
[알고리즘] 선택 정렬(Selection Sort) (0) | 2022.04.27 |
[알고리즘] 버블 정렬 (Bubble Sort) (0) | 2022.04.26 |
[알고리즘] 공간 복잡도 (Space Complexity) (0) | 2022.04.24 |
[알고리즘] 시간 복잡도(Time Complexity) (0) | 2022.04.24 |
댓글