코드잇 알고리즘(3) - 알고리즘 성능 평가

알고리즘 성능을 평가하기 위해서 시간 복잡도(Time Complexity)라는 개념 사용

시간 복잡도: 데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는가

• input 크기에 비레하는 알고리즘의 실행 시간
• 시간 복잡도가 작다 -> 더 빠른 알고리즘
  시간 복잡도가 크다 -> 더 느린 알고리즘
• Big-O 표기법을 사용한다.

---

알고리즘이 차지하는 메모리를 나타내기 위해 공간 복잡도(Space Complexity) 사용

공간 복잡도: input 크기에 비례해서 알고리즘이 메모리 공간을 얼마나 사용하는가

• 점근 표기법으로 표현할 수 있다.
• Big-O 표기법을 사용할 수 있다.

---

알고리즘의 효율성을 표현할 때는 점근 표기법(Big-O) 사용

점근 표기법: n이 엄청 크다는 가정 하에 소요 시간에서 가장 영향력이 큰 n의 지수만 남기는 것

• n이 엄청 큰 경우에 알고리즘의 소요 시간이 급격히 증가하기 때문에 n이 크다고 가정한다.
• 절대적인 시간이 아닌 성장성에 집중
• input 크기와 상관 없이 실행되는 코드만 O(1)

n(input list 길이)	O(1)	O(n)	O(n^2)	O(n^3)
100(기준)	1초	1초	1초	1초
200	1초	2초	4초	8초
1000	1초	10초	100초	1000초
10000	1초	100초	10000초	1000000초

시간은 기준이 되는 리스트의 길이의 n배가 될 때 n, n^2, n^3배 시간이 소요된다.

단순히 리스트의 길이에 따라서만 변하는 것이 아니라 컴퓨터의 성능에 따라서도 걸리는 시간이 달라진다.

 

---

List, Dictionary operation의 시간 복잡도

List Operations (리스트 길이가 n일 때)			Dictionary Operations
Operation	Code	Average Case	Operation	Code	Average Case
인덱싱	list[index]	O(1)	값 찾기	dict[key]	O(1)
정렬	list.sort( ) sorted(list)	O(n lg n)	값 넣기/덮어쓰기	dict[key] = value	O(1)
뒤집기	list.reverse( )	O(n)	값 삭제	del dict[key]	O(1)
탐색	element in list	O(n)
끝에 요소 추가	list.append(element)	O(1)
중간에 요소 추가	list.insert(index, element)	O(n)
삭제	del list[index]	O(n)
최솟값, 최댓값 찾기	min(list) max(list)	O(n)
길이 구하기	len(list)	O(1)
슬라이싱	list[a:b]	O(b-a)

 

주요 시간 복잡도

보통 사용되는 것들은  O(1), O(lg n), O(n), O(n lg n), O(n^2), O(n^3) 정도이다.

O(1)

• input 크기가 소요 시간에 영향을 주지 않는 경우
• 반복문이 없으면 대체로 O(1)이다.

O(n)

• 반복문이 있고, 반복되는 횟수가 input의 크기에 비례하는 경우
• n/2번 반복하는 경우
• 3n번 반복하는 경우 

O(n^2)

• 반복문이 연속해서 나오는 것이 아니라 반복문 안에 반복문이 포함된 경우(두 반복문 다 input 크기에 비례)

O(n^3)

• input 크기에 비례하는 반복문이 3번 중첩된 경우

O(lg n)

• lg n 은 밑이 2인 log
• input을 2로 계속 나누는 것을 반복하는 경우 혹은 2로 계속 곱하는 것을 반복하는 경우
• 계속해서 반씩 나누는 경우(이진 탐색법)

O(n lg n)

• input 크기에 비례하는 반복문 안에 lg n번 반복하는 반복문이 들어있는 경우
• lg n번 반복하는 반복문 안에 input 크기만큼 반복하는 반복문이 들어있는 경우