Basic of Algorithm
알고리즘의 기초
주어진 문제를 풀기 위한 명령어들의 단계적 나열
- 입출력
- 0개 이상의 외부 입력 → 1개 이상의 출력
- 명확성 - 각 명령은 모호하지 않고 단순 명확해야 함
- 유한성 - 한정된 수의 단계를 거친 후에는 반드시 종료
- 유효성 - 모든 명령은 컴퓨터에서 수행 가능해야 함
⇒ 하나 이상의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한 개의 명령들을 순서적으로 구성한 것
- 실용적 관점: 효율적이어야 함
알고리즘 생성 단계
설계 → 표현/기술 → 정확성 검증 → 효율성 분석
알고리즘의 설계
ex) 최댓값 찾기
1) 값들을 하나씩 모두 비교해가면서 찾는 방법
2) 토너먼트식 방법
→ 1): 순차탐색 2): 이진탐색
⇒ 무엇이 더 효율적인가? 둘은 조건이 다름. 1)의 경우 랜덤식 배열, 2)의 경우 순차적 배열이라는 조건이 있음
따라서, 주어지는 문제 속성 조건 등이 매우 다양하기 때문에 범용적인 설계 기법은 미존재
but, 대표적인 알고리즘 설계 기법
- 분할정복 방법(divied-and-conqure)
- 동적 프로그래밍 방법(dynamic programming)
- 욕심쟁이 방법(greedy)
알고리즘 분석
-
정확성 분석
유효한 입력, 유한시간 내에 정확한 결과 생성 여부
- 다양한 수학적 기법을 사용, 이론적 증명이 필요
-
효율성 분석
- 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
- 메모리 양 → 공간 복잡도(space complexity)
- 정적 공간 + 동적 공간(컴파일 할 때의 필요 공간 + 실행할 때의 필요 공간)
- 수행 시간 → 시간 복잡도(time complexity)
시간 복잡도
구현한 알고리즘을 컴퓨터에서 실행시켜 실제 수행 시간을 측정하는 방식이 아님.
⇒ 알고리즘의 단위 연산의 수행 횟수의 합
- 시간 복잡도에 영향을 미치는 요인
-
입력 크기
→ 입력으로 제공되는 데이터의 크기, 문제가 해결하려는 대상이 되는 개체의 개수
(행렬의 크기, 리스트 원소의 수, 그래프 정점의 수 등)
-
입력 데이터의 상태
→ 입력 크기 n이 증가하면 수행 시간도 증가
⇒ 단순히 수행되는 단위 연산의 개수의 합으로 표현하는 것은 부적절
⇒ 입력 크기 n에 대한 함수 f(n)으로 표현
→ 입력 데이터의 상태에 종속적
- 평균 수행 시간
- 최선 수행 시간
-
최악 수행 시간 (수행 시간이 가장 안 좋은 경우)
: 최악 수행 시간을 시간 복잡도로 사용
-
시간 복잡도 구하기
f(n) = 3n + 5 ——(점근성능)→ O(n)
점근성능
입력크기 n이 무한대로 커짐에 따라 결정되는 성능
ex) f(n) = 10n+9 f(n)=n2/2+3n
- 데이터가 15개 이하인 경우 왼쪽이 성능이 더 좋음(합이 더 작음), 반면 16개 이상인 경우 오른쪽이 성능이 더 좋음
ex) f(n) = 2$n2$ + 5n + 200
- n이 커지면 커질수록 1번 항(최고차항)이 최고항이 됨
⇒ 점근성능의 결정방법: 수행 시간의 다항식 함수에서 최고차항($n2$)만을 계수 없이 취해서 표현
-
수행 시간의 정확한 값이 아닌 어림값 → 수행시간의 증가 추세를 파악하기 용이하다.
→ 알고리즘의 우열 표현에 용이함
점금성능의 표기법
- 점근적 상한(최악의 경우 - Big-O)
함수 f와 g를 각각 양의 정수를 갖는 함수라고 한다면,
어떤 양의 상수 c와 $n0$이 존재하여 모든 n≥$n0$에 대하여 f(n)≤cg(n)이면 f(n)=O(g(n))이다.
(구한 알고리즘 f(n)이 최악의 경우에도 cg(n)보다 안 좋아질 수 없을 때, f(n)=O(g(n)))
- 점근적 하한(최선의 경우 - Big-omega)
함수 f와 g를 각각 양의 정수를 갖는 함수라고 한다면,
어떤 양의 상수 c와 $n0$이 존재하여 모든 n≥$n0$에 대하여 f(n)≥cg(n)이면fn(n)=****Big-Ω****이다.
(구한 알고리즘 f(n)이 최선의 경우에도 cg(n)보다 더 좋아질 수 없을 때, f(n)=****Big-Ω****)
- 점근적 상하한(상한과 하한을 모두 갖고 있는 경우 - Big-theta)
함수 f와 g를 각각 양의 정수를 갖는 함수라고 한다면,
어떤 양의 상수 c1, c2와 $n0$이 존재하여 모든 n≥$n0$에 대하여 c1g(n)≤f(n)≤c2g(n)이면fn(n)=****Big-θ****이다.
(구한 알고리즘 f(n)이 최선의 경우에도 cg(n)보다 더 좋아질 수 없을 때, f(n)=****Big-θ****)
⇒ 최고차항(상한), 최저차항(하한) n을 가져와 해당 기호 표기에 넣어주면 된다.
10n+9 → O(n)
n2/2+3n → O(n2)
O-표기 간의 연산 시간의 크기 관계
- 빅오표기법
-
시간 복잡도를 계산할때 상대적으로 불필요한 연산은 제거하여 알고리즘을 분석하여 좀더 간편하게 시간 복잡도를 표기하는 방법
양의 정수 n을 n번 곱하는 경우
n*n = 2t = O(n)
n을 n번 더함 = (2n+1)t = O(n)
n*n번 1을 더함 = (2n2+1)t = O(n2)
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)
Better O(1) < O(log n) < O(n) < O(n×log n) < O(n2) < O(2n) < O(n!) Worse
상수 함수 < 로그 함수 < 선형 함수 < 다항 함수 < 지수 함수 < 재귀 함수
-
👇더 자세한 설명
O(n) :
- Linear 한 그래프가 그려진다.
- 데이터 양에 시간이 정비례한다.
- for문을 통한 탐색
O(n log n) :
- 데이터 양이 n배 많아진다면 실행시간은 n배보다 log n 배 더 많아진다.
- Quick sort, merge sort
O(n^2) :
- 데이터 양에 따라 걸리는 시간은 n의 제곱에 비례하게 된다.
- 2중 for문
- bubble sort, insertion sort
-
대개 이와 같은 경우에는 시간 초과가 발생한다.
void re(){ for (int i=0;i<N;i++){ for (int j=0;j<N;j++){ i++; } } }
O(2^n) :
- 급격하게 복잡도가 증가한다
-
피보나치 수열이 그 예
void fibonacci(int n, int r){ if (n<=0) return 0; else if (n==1) return r[n] = 1; return r[n] = fibonacci(n-1,r) + fibonacci(n-2,r); }
알고리즘의 시간복잡도 구하기
-
알고리즘의 수행시간 f(n)을 구한 후, f(n) = O(g(n))을 만족하는 최소 차수의 함수 g(n)을 찾는다.
알고리즘에 나타난 루프의 반복횟수를 조사하여 시간복잡도를 취한다.
i = 1; // 1 while(i <= n) { // n + 1 x = x+1; // n i = i+1; // n }⇒ 3n + 2 → O(n)
int i, j; for(i = 1; i <= n; i++) // n for (j = i; j <= n; j++) // n if (j > i) C[ij] = A[i]*B[j];⇒ O(n2)
순환 알고리즘의 성능
순환(recursion, 재귀)
알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태
점화식 표현
T(n) = T(n/2) + O(1), T(1)=c1
(*T(n) Time Complexity: 알고리즘을 수행하는데 이루어지는 연산 (산술, 대입, 비교, 이동)수)
data n개를 찾는데 걸리는 시간 = n/2개를 찾는 데 걸리는 시간 + 상수시간(무조건 걸리는 시간)
-
기본 점화식과 폐쇄형
- 2) 퀵 정렬의 최악의 수행 시간
- 3) 이진 탐색의 수행 시간
- 6) 합병 정렬의 수행시간, 퀵 정렬의 최선의 수행시간