📌 Chapter 1 - 알고리즘 효율성과 분석
📚 알고리즘의 유래
-
알콰리즈미 : 이름이 라틴어로 변환되면서 알고리즘이라는 용어를 쓰게됨
-
최초의 알고리즘은 유클리드의 최대 공약수 알고리즘 이다.
: 2개의 자연수의 최대 공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대 공약수와 같다!ex) (18,6) == (12,6) == (6,6) == (0,6)
두 수 중 하나가 0이 됐을 때 나머지 값이 최대 공약수!
📚 알고리즘 이란?
- 문제에 대한 답을 찾기 위한 체계적인 문제해결절차
- 항상 효율적인 알고리즘을 고안하는 것이 매우 중요하다
- A set of unambiguous instructions for solving a problem or subproblem in a finite amount of time using a finite amount of data
📚 알고리즘 특성
- 정확성 / 수행성 / 유한성 / 효율성 (시간, 공간 복잡도)
📝 최댓값 찾기
- 순차탐색 : 숫자를 하나씩 비교해가면서 가장 큰 숫자를 변수에 넣어 진행하는 방법
📝 임의의 숫자 찾기
- 순차탐색 (Sequential Search)
: n - 이분탐색 (Binary Search)
: log n +1
: 정렬이 되어있다면 이분탐색이 훨씬 효율적이지만, 정렬이 되어있지 않다면 순차탐색이 더 효율적이다. 즉, 자료가 어떻게 구성되어있느냐에 따라 효율성이 다르다.
📚 알고리즘 수행시간
- 알고리즘의 수행시간을 좌우하는 기준은 다양하게 잡을 수 있다.
(for 루프의 반복횟수, 함수의 호출 횟수 등)
ex) for 루프 n^2 x 최대값 구할때 적어도 n/2 == n^3
sample(A[],n){ sum=0; for i = 1 to n for j = 1 to n{ k= A[1 ~ n] 에서 임의로 n/2 개 뽑았을 때 최대값; sum=sum+k; } return sum; }
📝 피보나치
- 재귀적 방법
int fib(int n){
if(n<=1)
return n;
else
return (fib(n-1)+fib(n-2));
}- fib(n)의 함수 호출 횟수 계산
T(n) : fib(n)을 계산하기 위하여 fib함수를 호출하는 횟수
T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2) +1 (처음 실행했으니까)
> T(n-2) + T(n-2) == 2xT(n-2)
📌 T(n-1) > T(n-2) 이므로!!
📌 T(n-2) = T(n-3) + T(n-4) +1 > 2 x T(n-4)
> 2^2 X T(n-4)
> 2^3 X T(n-6)
.
.
.
> 2^n/2 X T(n-n) = 2^n/2 X T(0) = 2^n/2: T(n) > 2^n/2
: 피보나치 재귀 알고리즘은 수행속도가 매우 느리다. 왜? 중복계산이 너무 많아서
- 반복적 방법
int fib2(int n){
index i;
int f[0~n];
f[0]=0;
if(n>0){
f[1]=1;
for (i=2; i<=n; i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}: T(n) = n+1
: 중복계산을 하지 않기 때문에 훨씬 빠르다
FE Programmer