알고리즘 평가 주의 사항

점근 표기법으로 알고리즘을 평가할 때 주의해야 할 점 몇 가지만 알아봅시다.

 

점근 표기법에서 n은 무엇인가?

 

점근 표기법에서 n이 갖는 의미에 대해 착각하는 사람들이 많습니다. 하지만 사실 n은 점근 표기법에서 인풋 크기를 나타낼 때 가장 흔히 사용되는 문자일 뿐, 별다른 의미는 없습니다. 인풋 리스트의 크기를 x라고 부르기로 하면 O(lgx), O(x), O(x^2) 등의 표기를 하겠죠.

 

“트리”나 “그래프” 같은 조금 특수한 자료 구조가 인풋으로 들어올 수도 있습니다. 트리와 그래프가 특수한 이유는 리스트처럼 “선형적”이지 않기 때문인데요. 예를 들어서 그래프는 꼭짓점(vertex)과 변(edge)으로 이루어져 있습니다. 꼭짓점의 개수를 V라고 하고 변의 개수를 E라고 하면, 두 꼭짓점 간 최단 경로를 찾는 BFS 알고리즘의 시간 복잡도는 O(V+E)입니다. 시간 복잡도를 표현하기 위해 두 개의 다른 문자를 쓴다는 점에서 조금 특이하네요.

 

(참고: "트리"나 "그래프"라는 개념을 몰라도 전혀 관계 없습니다.)

 

아마 많은 경우 주로 n을 사용하겠지만, n에 특별한 의미를 둘 필요는 없습니다!

코드의 모든 줄은 O(1)인가요?

 

아닙니다!

 

인풋 크기와 상관 없이 실행되는 코드만 O(1)입니다. 그렇지 않은 코드는 시간 복잡도를 따져봐야 합니다.

 

예를 들어서 sorted 함수나 sort 메소드를 사용하면 내부적으로 O(nlgn)의 정렬이 이루어집니다.

 

만약 리스트에서 in 키워드를 통해 값의 존재 여부를 확인하면 내부적으로 O(n)의 선형 탐색이 이루어집니다.

 

그 외에도 알아야 할 것들이 많은데, 일단은 아래의 몇 가지만 알아두세요.

 

List Operations

 

리스트의 길이를 n이라고 합시다.

Operation	Code	Average Case
인덱싱	my_list[index]	O(1)
정렬	my_list.sort() sorted(my_list)	O(nlgn)
뒤집기	my_list.reverse()	O(n)
탐색	element in my_list	O(n)
끝에 요소 추가	my_list.append(element)	O(1)
중간에 요소 추가	my_list.insert(index, element)	O(n)
삭제	del my_list[index]	O(n)
최솟값, 최댓값 찾기	min(my_list) max(my_list)	O(n)
길이 구하기	len(my_list)	O(1)
슬라이싱	my_list[a:b]	O(b−a)

Dictionary Operations

Operation	Code	Average Case
값 찾기	my_dict[key]	O(1)
값 넣어주기/덮어쓰기	my_dict[key] = value	O(1)
값 삭제	del my_dict[key]	O(1)

 

출처 코드잇