그림 출처: https://www.inflearn.com
알고리즘은 간단히 말해 어떤 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는
잘 정의된 계산 절차를 말한다.
그리고 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료할 경우 이를 '타당하다'고 하며 , 그 타당한
알고리즘이 주어진 계산 문제를 푼다고 말한다.
지금 부터 이러한 알고리즘에 대해서 간단한 예를 설명 하겠습니다.
2. 정렬
2.1) 삽입 정렬
하나의 storage에 비교할 값을 넣고 바로 전 인덱스 부터 대소를 비교하며 차례대로 이동하는 형식이다.
따라서 기준점(*)을 기준으로 왼쪽은 정렬이 되어져 있고 오른쪽은 정렬되지 않았다.
의사코드를 보면
이러한 값이 된다.
여기서 잠깐 이 의사코드가 맞는지 확인 하기 위하여 루프 불변셩에 대해서 알아보자
루프 불변성은 알고리즘이 타당한 이유를 쉽게 이해할 수 있도록 하기 위해 사용된다.
이 루프 불변성을 보이려면 세 가지 특성을 만족하면 되는데
초기 조건 - 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다.
유지 조건 - 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도
계속 참이어야 한다.
종료 조건 - 루프가 종료될 때 그 불변식이 알고리즘의 타당성을 보이는데 도움이 될 유용한
특성을 가져야 한다.
여기서 앞의 두 조건을 만족하면 루프가 반복을 시작할 때 루프 불변성은 항상 참이다.
삽입 정렬을 예로 들면
1. 루프의 첫 반복 j=2일때 루프 불변성이 성립하는지 보자.
간단하가 처음일 때 A[1] 만 존해고 이는 정렬 되었다고 볼수 있으므로 루프 불변성이 성립한다.
2. 다음으로 매번 반복 시 루프 불변성이 유지되는지를 보자
이 역시 간단하다. 의사 코드를 보면 A[j] (key) 값이 올바른 위치를 찾을 때 까지 j-1,j-2,j-3...을
오른쪽으로 한 자리 씩 움직이게 된다.( A[i+1] = A[i]) 그리고 마지막에는 같은
원소이지만 정렬 된 값을 가지게 되므로 루프 불변성이 유지된다.
3. 3은 2와 같다 종료 상황시 루프 불변성이 유지됨을 보이면 된다. 범위는 1~n이 될것이다.
지금 의사코드는 맞는지를 확인 해봤으니 이 알고리즘을 분석해 보자.
알고리즘을 분석할 때는 수행시간을 입력 크기의 함수로 표현 한다( T(n) )
이를 위해 수행시간과 입력크기를 알아야 하는데
입력 크기는 일반적으로는 입력 항목의 개수 이다. 또 이진수의 비트(bit) 인 경우 필요한 총 비트수가 될수 있다.
수행 시간은 실행된 단계의 횟수를 말한다. 의사코드의 각 행을 수행하는 데 상수 시간이
소요 된다고 생각 하면된다. 보통 상수시간(c)와 횟수(times)로 계산한다.
알고리즘의 수행시간은 각 명령문 수행시간의 합이다. 이를 주의하자
수행시간이 ci 단계 만큼 걸리는 명령문이 n번 실행된다면 총 수행시간은 ci n 이 된다
이를 T(n)에 대해 정리 하면
이 된다
그리고 여기서 c(5,6,7) 의 식에 대해서 best&worst case 로 나뉘어게 된다.
best case의 경우 while문이 조건식 비교의 순간 단 한번 돌게 되므로 c(6,7)은 0이 되어진다.
즉
그리고 worst case는 전부 도는 경우로 1 ~ j-1 까지 모두 돌게 되어진다.
vWorst case
빅오는 O(n^2)이 된다.
따라서 이에 대응하는 의사코드를 보면
그리고 분할정복 방법론의 시간 복잡도 함수 로 나타내면
알고리즘 공부 <5> - 퀵 정렬 (0) | 2018.10.07 |
---|---|
알고리즘 공부 <4> - 힙정렬 (0) | 2018.09.22 |
알고리즘 공부<3> - 빅오를 찾는 과정? (2) | 2018.09.10 |
알고리즘 공부 <2> - 빅오? 오메가? 세타? 점근적? (0) | 2018.09.07 |
달팽이 알고리즘 (0) | 2018.07.12 |