알고리즘의 분석과 수행시간
알고리즘의 분석
- 알고리즘 실행하는데 필요한 자원을 예측하는 것.
- 여러 측정 관심대상이 있지만 대부분 측정 대상은 계산 시간.
- 수행시간 : 기본 연산 개수 or 실행된 단계의 횟수
-> 각 명령문 수행 시간의 합 - 알고리즘 수행시간 : 주어진 문제의 입력 크기가 다양해서 최악, 최상, 평균 적인 경우 총 3갱우가 있는데 "최악"이 관심가질만 하다.
시간복잡도
- 알고리즘 수행시간 기준.
- 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현.
<시간 복잡도와 입력 크기의 관계>
- 시간복잡도가 높다는 것 : 입력의 크기가 증가할 때마다 수행시간 역시 증가한다는 것.
- 시간 복잡도가 낮다고 해서 언제나 빠른 건 아니다.
- 입력의 크기가 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠를 수 있다.
시간 복잡도 표기를 쉽게 하기 위해 증가차수, 점근적 효율성을 기준으로 알고리즘 수행시간을 나타냄.
증가차수
더 단순하게 추상화하여 수행 시간에 대한 증가비율 또는 증가차수를 이용하는 것.
차수가 가장 높은 항만 고려하고 상수 계수는 무시한다.
점근적 효율성
입력크기가 극한으로 증가할때 어떤 알고리즘의 수행시간이 어떻게 증가하는지에 관심. 점금적으로 더 효율적인 알고리즘이 가장 좋은 선택이 된다.
표기방식에 따라
- 최상 : 오메가 표기법
- 평균 : 세타 표기법
- 최악 : 빅오 표기법
이 중, 최악을 나타내는 빅오를 사용해 최악의 경우를 판단하여 평균과 가까운 성능으로 예측하기 쉽다.
빅오 표기법 (Big-O Notation)
- 점근적인 상한을 나타낸다.
- 입력의 크기가 극한으로 증가 할때, 최고 차항의 차수가 가장 영향을 많이 끼치기에 가장 높은 항을 제외하고 다른 항은 다 제거하는 표기법.
즉, 시간복잡도에 가장 큰 영향을 미치는 차항으로 시간복잡도를 나타내는 표기법.
T(n)=n^2+2n+9 # O(n2)
T(n)=n^4+n^3+n^2+1 # O(n4)
T(n)=5n^3+3n^2+2n+1 # O(n3)
알고리즘의 시간복잡도는 반복문에 의해 결정되므로 반복문이 몇번 실행되는지 보면된다.
for(int i=0; i<N; i++){
...
for(int k=0; k<N; k++){
...
}
}위와 같은 코드의 경우, 반복문이 2번 실행되었음으로 시간복잡도는 O(N^2) 이다.
Big-O 표기법의 종류와 성능
종류)
- O(1) - 상수 Constant
- 입력되는 데이터양과 상관없이 일정한 실행시간을 가진다.
- 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다. - O(logN) Logarithmic
- 데이터 양 많아져도 시간은 조금씩 증가한다.
- 시간에 비례하여, 탐색 가능한 데이터 양이 2의 n승이 된다.
- 문제 해결에 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
- 만약 입력자료의 수에 따라 실행시간이 이 log N의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다.
- 이 유형은 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타난다.
ex) Binary Search
- O(N logN) log linear
- 데이터 양이 N배 많아진다면, 실행 시간은 N배보다 조금 더 많아진다.(정비례X)
- 이 유형은 커다란 문제를 독립적인 작은 단위로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우.
- N이 두배로 늘어나면 실행 시간은 2배보다 약간 더 많이 늘어난다.
ex) Quick Sort, Merge Sort
- O(N^2) Quadratic
- 데이터야에 따라 걸리는 시간은 제곱에 비례(효율좋지않아 사용하면안된다)
- 이 유형은 이중 루프내에서 입력 자료 처리하는 경우 나타난다.
- N값이 큰 값이 되면 실행시간은 감당하지 못할 정도로 커지게 된다.
- 문제 해결을 위해 단계의 수는 입력값 n의 제곱
ex) 이중 for문을 사용하는 bubble sort, 삽입 정렬
성능 비교
developer