알고리즘 분석 (Algorithm analysis)
- ETC
- 2018. 11. 29.
알고리즘 분석 (Algorithm analysis)
시간 복잡도 분석 (Time complexity analysis)
✐ 알고리즘의 실행 시간 효율성 분석
✓ 알고리즘의 실제 수행시간을 측정하는 방법 : 실행환경의 영향이 크다.
✓ 시간복잡도 분석은 명령문의 실행 횟수를 분석한다.
✐ 실행시간은 입력(Input)에 따라 달라진다.
✓ 입력크기가 클수록 증가한다.
✓ 동일한 입력 크기라도 입력 사례에 따라 달라질 수 있다.
✐ 입력 크기(Input size) : n으로 표시한다.
✓ 검색 혹은 정렬 문제 : 배열에 속한 원소(Element)의 수
✓ 피보나치 수열 혹은 팩토리얼 계산 : 입력을 부호화하는데 필요한 비트 수 = logN + 1
✐ 시간복잡도 분석은 입력 크기에 따른 실행시간을 중요, 연산의 수행 횟수로 계산
✓ 입력 크기에 따른 연산의 수행 횟수가 일정하지 않는 경우는 주로 최대 실행 횟수 혹은 평균적 실행 횟수를 고려한다.
✓ 주로 T(n)으로 표기, 최대 실행 횟수는 W(n), 평균 횟수는 A(n)으로 표기
복잡도 카테고리 (Complexity category)
✐ 시간 복잡도의 최고차항의 상수를 무시하고 표시하는 것, Big-O 표기법
(Example)
✐ 입력 크기 n과 상관없는 상수시간 : O(1)
sample1(A[1...n]) k = [n/2]; return A[k]; |
=> T(n) = c = O(1)
✐ 단순 반복(Simple iteration)은 반복 횟수에 비례하는 시간이 소요
sample2(A[1...n]) tmp = 0; for i = 1...n // for문은 n에 비례하는 시간이 소요 if(A[i]>0) tmp += A[i]; return tmp; |
=> T(n) = n + 2 = O(n)
✐ 중첩 반복(Nested iteration)의 경우, 먼저 내부 반복(Inner loop)의 횟수를 계산 후 이에 대하여 외부 반복(outer loop) 횟수를 계산
sample3(A[1...n]) sum = 0; for i = 1...n for j = 1...i sum = sum + A[i] + A[j]; return sum; |
=> T(n) = n(n+1)/2 = O(n^2)
✐ 단순 반복처럼 보이지만, 실제는 중첩 반복인 경우
sample4(A[1...n]) sum = 0; for i = i...n k = A[1...i]의 최대값; // i에 비례하는 시간 소요되는 반복 연산 sum += k; return sum; |
=> T(n) = n(n+1)/2 = O(n^2)
✐ 두 개 이상의 반복이 연속되는 경우, 차수가 더 높은 반복의 차수가 전체 차수가 됨
sample5(A[1...n]) sum1 = 0; for i = 1...n // n에 비례하는 시간 소요 sum1 += A[i]; sum2 = 0; for i = 1...n // n^2에 비례하는 시간 소요 for j = i ... n sum2 = sum2 + A[i] + A[j]; return sum1 + sum2; |
=> T(n) = O(n) + O(n^2) = O(n^2)
✐ 반복의 횟수가 일정 비율로 줄어드는 경우, 차수는 로그(logarithmic)
sample6(A[1...n]) j = n; while(j >= 1) A[j]를 출력; j = [j/2]; |
=> T(n) = O(log_2 n)
✓ n = 2^5이라고 가정하면, j = 2^5, 2^4, ..., 2, 1이므로 반복횟수는 6번
✓ n = 2^k (<=> log_2 n)이라고 가정하면, j = 2^k, 2^(k-1), ..., 2, 1이므로 반복회수는 (k+1)번
References. 2017 알고리즘 강의 <0장. 알고리즘 기초> - 강영경 교수
✔︎ 오타, 틀린 개념이 있을 경우 댓글 달아주세요~!
(확인 후 수정하도록 하겠습니다~^^)
✔︎ 추가할 개념이 있다면 댓글 부탁드립니다~!
(지식을 공유해주세요~^^)
