알고리즘의 분석
✔ 알고리즘을 작성하는데는 어떠한 naming을 하냐도 중요한 요소로 작용한다
알고리즘 분석에 있어 고려해야할 것
1. 문제를 푸는데 요구되는 메모리 공간
2. 실행시간
그런데 이러한것을 측정할때 컴퓨터의 성능 및 프로그램, 언어에 의해서 속도가 달라질수 있다
따라서 우리는 공통된 측정방법이 필요하고 그게 바로
Big-O Notation이다.
Big-O Notation
할당문의 갯수를 계산해주면 되는데
이때 data의 규모가 커질수록 step의 수가 증가하고 함수 또한 빠르게 증가하므로
정확한 값보다는 비교를 위한 근사값을 사용한다.
e.g) n^2+1 , n^2 은 n의 갯수가 증가할수록 뒤에 붙은 1의 영향은 미미해진다
또한 n^2과 2n^2도 n의 갯수가 증가함에 따라 계수는 무시할 수 있을 영향력을 가진다.
따라서 7n^2 + 10n + 5의 경우 O(n^2)만 유의미한 값으로 근사치를 잡아준다
그런데 이렇게 계산을 함에 있어서 data set의 종류에 따라 best case 가 나타날수도 있고
worst case 가 나타날수도 있는데 우리는 일반적으로 average case를 생각하도록 한다
(n logn 과 n^2 중 누가 더 연산속도가 느린지 확인 할때는 임의로 특정 수를 넣어서
비교를 해주면 된다 예를 들어 n이 10일때 n logn은 10이 되고 n^2는 100이다.
따라서 n^2가 더 느린 것이다.)
Big-O를 이용한 알고리즘 분석 예시
Anagram 이라는 게임을 예로 들어보자.
(Anagram은 대기 - 기대 이와 같이 순서를 바꾸어 단어를 만드는 게임)
1. Checking Off : O(n^2)
A 단어와 B단어(list로 바꿔준다)에 대해서 A 단어의 0번째 index부터
B단어의 index들과 차근차근 비교하며 같은 character 를 발견하면 B의 해당 index의
문자를 None 으로 바꾼다. 만약 찾지 못하면 특정 flag를 false로 변경해주고 return한다
A의 한 index당 B의 index전체를 비교하므로 n*n n^2만큼 비교가 들어가게 된다.
2. Sort and Compare : O(n^2) or O(n logn)
A단어와 B단어를 list화 해준다음 sort를 이용해 정렬을 해주고 두 list의 index를 차례차례 학인해주며
같은 index에 다른 글자가 오면 다른 글자 조합인게 되므로 False를 반환해준다.
얼핏 보면 sort후 반복문을 통해 index비교를 해주기 때문에 O(n)만 볼수 있는데
sort자체가 O(n^2) or O(n logn)를 가지기에 여기에 집중해야한다
3. Brute Force : O(n!)
A단어를 구성하고 있는 문자열로 생성할수 있는 모든 단어를 생성한 뒤에 B가 그 안에 있는지 확인해주는 방법
A단어의 글자수가 n이면 첫째자리에 올수 있는 경우의수 n, 둘째 자리 n-1.... 처럼 이루어 지기때문에 n! 이 오게되고
n! 이라는 복잡도는 10!만 해도 어마어마해지기때문에 심지어 2^n 보다 안 좋은 효율이다.
4. Count and compare : O(n)
A단어와 B단어의 문자수를 저장할 수 있는 list를 생성하여 해당 문자가 발견될때 마다
list의 count를 늘려간다.
이 때 A와 B 다른 list를 구성하게 되므로 반복문은 중첩이 아니라 따로 구성이 되고
A, B의 문자수 list의 생성이 끝나면 반복문을 통해 index를 비교해가며 다르면
Anagram의 결과가 틀렸다고 해주면 된다.
단 위의 4번과 같은 경우에는 연산속도를 좋지만
메모리 공간을 사용함에 있어서는 추가 list를 만드는 행위 등으로 더 많은 소요가 있다.
따라서 이를 잘 절충하여 코드를 짤 필요가 있겠다.
위의 결과처럼 code의 구성 자체에서 성능의 차이를 불러 올수 있지만 python의 자료구조가 가지고 있는 operator의 차이로 인해 연산속도의 차이가 나는 경우도 있다.
특히 구성되는 과정에서 일반적으로 많이 사용하는 operation의 효율성을 위해 덜 사용되는 operation의 효율이 희생되기도 했다.
따라서 적절한 tool을 사용하는 것은 중요하다
python의 주요 데이터 구조의 시간복잡도
1. List
e.g ) 양의정수 list를 만드는 4가지 방법
1. concat (아주 느림)
list1 = []
for i in range(100):
list1 = list1 +[i]
2. append (일반적인 for문으로 만드는 방법)
list2 = []
for i in range(!00):
list2.append(i)
3. list comprehension (append에 비해 2배가량 빠름)
list3 = [ i for i in range(100)]
4. list range (가장 빠름)
list4 = list(range(100))
이처럼 똑같이 list를 만드는데 있어서도 연산속도의 차이가 많이 나기때문에 적절한 tool을 이용하는게 중요하다.
2. Dictionary
Dictionary도 List와 마찬가지로 index 와 set에 있어서 O(1)만큼의 효율을 보이나
하지만 중요한 것은 contain 여부를 확인하는 것도 Dictionary에서는 O(1)이라는 것이다.
시간 복잡도와 관련하여 추가 사항은 Time Complexity Wiki 를 참고하도록 하자.
댓글 없음:
댓글 쓰기