[알고리즘] 점근 표기법

점근표기법이란?

• 알고리즘의 성능을 수학적으로 표기하는 방법
• 알고리즘의 “효율성”을 평가하는 방법
• 빅오(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