Algorithm : 1~4 summary

LeemHyungJun·2023년 4월 23일
0

Algorithm

목록 보기
5/9

1. Algorithm: efficiency, analysis and order

1-1. 순차검색 알고리즘

  • pseudo code
void seqsearch(int n, const keytype S[], keytype x, index& location)
{
	location = 1;
    while(location <= n && S[location] != x)
    {
    	location++;
    }
    if(location > n)
    {
    	location = 0;
    }
}
  • 시간 복잡도
    • 최악의 경우 n : 찾는 데이터가 없거나 맨 뒤에 있을 때
      • O(n)O(n)
    • 평균의 경우 (x가 배열안에 있을 때만 고려)
      • 단위연산은 S[location] != x 비교
      • x가 배열의 k번째 있을 확률 1n\frac{1}{n}
      • x가 배열의 k번째 있다면.. k번 수행해야함
      • A(n)=k=1n(k×1n)=1n×n(n+1)2=n+12A(n) = \sum_{k=1}^{n}(k\times \frac{1}{n})=\frac{1}{n}\times \frac{n(n+1)}{2} = \frac{n+1}{2}
    • 평균의 경우 (x가 배열안에 없을 때도 고려)
      • x가 배열 안에 있을 확률이 p
      • x가 배열의 k번째 있을 확률 pn\frac{p}{n}
      • x가 배열에 없을 확률 1p1-p
      • A(n)=k=1n(k×pn)+n(1p)=n(1p2)+p2A(n) = \sum_{k=1}^n(k\times\frac{p}{n})+n(1-p)=n(1-\frac{p}{2})+\frac{p}{2}
    • 최고의 경우
      • B(n)=1B(n)=1

1-2. 배열의 수 더하기

  • pseudo code
number sum(int n, const number S[])
{
	index i;
    number result;
    result = 0;
    for(i=1; i<=n; i++)
    {
    	result = result + S[i];
    }
    return result;
}
  • 시간 복잡도
    • 덧셈이 단위연산: T(n)=nT(n)=n
    • 지정문이 단위연산: T(n)=n+n+1T(n) = n+n+1
    • 결론적으로는 O(n)O(n)

1-3. 교환정렬

  • pseudo code
void exchangesort(int n, keytype S[])
{
	index i, j;
    for(i=1; i<=n-1; i++)
    {
    	for(j=i+1; j<=n; j++)
        {
        	if(S[j] < S[i])
            {
            	exchange S[i] and S[j];
            }
        }
    }
}
  • 시간 복잡도
    • 단위연산: S[j]와 S[i]의 비교
      • T(n)=(n1)+(n2)+(n3)+..+1=n(n1)2T(n) = (n-1) + (n-2)+(n-3)+..+1 = \frac{n(n-1)}{2}
    • 단위연산: exchange 연산
      • 최악의 경우 (거꾸로 배열이 정렬된 경우)
      • W(n)=(n1)n2W(n) = \frac{(n-1)n}{2}
    • 결론적으로 O(n2)O(n^2)

1-4. 행렬곱셈

  • pseudo code
void matrixmult(int n, const number A[][], const number B[][], number C[][])
{
	index i,j,k;
    
    for(i=1; i<=n; i++)
    {
    	for(j=1; j<=n; j++)
        {
        	C[i][j] = 0;
        	for(k=1; k<=n; k++)
            {
            	C[i][j] = C[i][j] + A[i][k] * B[k][j];
            }
    	}
    }
}
  • 시간 복잡도
    • T(n)=nnn=n3T(n) = n*n*n=n^3
    • O(n3)O(n^3)

1-5. 이분검색 알고리즘 (재귀 x)

  • pseudo code (재귀 x)
void binsearch(int n, const keytype S[], keytype x, index& location)
{
	index low, mid, high;
    low = 1;
    high = n;
    location = 0;
    while(low <= high && location == 0)
    {
    	mid = (low+high)/2;
        if(x == S[mid])
        	location = mid;
        else if(x < S[mid])
        	high = mid - 1;
        else
        	low = mid + 1;
    }
}
  • 시간 복잡도
    • 최악의 경우에도 한번의 검색 시 절반씩 줄기 때문에
    • lg nlg\ n + 1

1-6. 피보나치 수열

  • pseudo code (재귀)
int fib(int n)
{
	if(n<=1)
    	return n;
    else
    	return fib(n-1) + fib(n-2);
}
  • 시간 복잡도
    • recurrence relation (재귀) : T(n)=T(n1)+T(n2)+1T(n) = T(n-1) + T(n-2) + 1
      -> 2n/22^{n/2}
  • pseudo code (재귀x)
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];
}
  • 시간 복잡도
    • recurrence relation (재귀x) : T(n)=n+1T(n) = n+1
      -> O(n)O(n)

1-7. 차수

limng(n)f(n)={c>0이면g(n)Θ(f(n))0이면g(n)o(f(n))이면g(n)ω(f(n))\lim_{n \to \infty}\frac{g(n)}{f(n)}= \begin{cases} c>0이면 & g(n)\in\Theta(f(n)) \\ 0이면 & g(n)\in o(f(n))\\ \infty 이면 & g(n)\in \omega(f(n)) \end{cases}

1-8. 알고리즘 복잡도와 컴퓨터 능력

  • ex1)
    • 알고리즘 복잡도가 cn일때 t시간동안 m개의 문제 해결
    • 처리속도가 2배가 된다면?
      • c(m+x)=2cm >x=m >m+m=2mc(m+x) = 2cm\ -> x = m\ -> m+m = 2m
  • ex2)
    • cn2cn^2 일때
    • 처리속도 4배가 된다면?
      • c(m+x)2=4cm2 >x=m >m+m=2mc(m+x)^2 = 4cm^2\ -> x = m\ -> m+m = 2m
  • ex3)
    • c2nc2^n 일때
    • 처리속도 2배
      • c2m+x=2c2m >c2m+x=c2m+1 >x=1 >m+1c2^{m+x} = 2c2^m\ -> c2^{m+x}= c2^{m+1}\ -> x = 1\ -> m+1
  • ex4: 15-1 기출)
    • c2nc2^n 일때 n=10 해결
    • 처리속도 10배
      • c2n+x=10c2n >c2n+x=c2n+log210c2^{n+x}=10c2^n\ -> c2^{n+x} = c2^{n+log_210}
      • log210=3.log_210 =3.xx -> 13 개
  • ex5)
    • O(n!)O(n!) T시간 n=10 해결
    • 처리속도 1000배
      • c(m+x)!=1000c(m)!c(m+x)! = 1000*c(m)! -> c(m+x)!=c(m+6.??)!c(m+x)!=c(m+6.??)!
      • 10+6 = 16개

2. Algorithm: divide and conquer

2-1. 이분검색 (재귀 o)

  • pseudo code
index location(index low, index high)
{
	index mid;
    
    if(low > high)
    	return 0;
    else
    {
    	mid = (low+high)/2;
        if(x == S[mid])
        	return mid;
        else if(x < S[mid])
        	return location(low, mid-1);
        else
        	return location(mid+1, high);
    }
}
  • 시간 복잡도
    • 최악의 경우(검색하는 반쪽 배열의 크기가 n/2인 경우)
    • W(n)=W(n2)+1W(n) = W(\frac{n}{2})+1, n>1, n=2k,W(1)=1n>1,\ n=2^k, W(1)=1
    • W(n)=lg n+1W(n) = lg\ n+1

2-2-1. 합병정렬 (공간 복잡도 2n)

  • pseudo code
void mergesort(int n, keytype S[])
{
	const int h=n/2;
    const int m=n-h;
    
    if(n>1)
    {
    	copy S[1] through S[h] to U[1] through U[h];
        copy S[h+1] through S[n] to V[1] through V[m];
        mergesort(h,U);
        mergesort(m,V);
        merge(h,m,U,V,S);
    }
}
void merge(int h, int m, const keytype U[], const keytype V[],keytype S[])
{
	index i, j, k;
    i = 1; j=1; k=1;
    while(i<=h && j<=m)
    {
    	if(U[i] < V[j])
        {	
        	S[k] = U[i];
            i++;
        }
        else
        {
        	S[k] = V[j];
            j++;
        }
        k++;
    }
    if(i>h)
    	copy V[j] through V[m] to S[k] through S[h+m];
    else
    	copy U[i] through U[h] to S[k] through S[h+m];
}
  • 시간 복잡도
    • 합병함에 있어서 최악의 경우 예시) U:4,5,6,7 V:1,2,3,8
    • W(h,m) = W(h)+W(m)+h+m-1
      -> W(n)=2W(n2)+n1Θ(nlg n)W(n) = 2W(\frac{n}{2})+n-1 \in \Theta(nlg\ n)

2-2-2. 합병정렬 (공간 복잡도 n)

  • pseudo code
void mergesort2(index low, index high)
{
	index mid;
    if(low<high)
    {
    	mid = (low+high).2;
        mergesort2(low, mid);
        mergesort2(mid+1, high);
        merge2(low,high,mid);
    }
}
void merge2(index low, index mid, index high)
{
	index i,j,k;
    keytype U[low..high];
    i = low;
    j= mid+1;
    k = low;
    while(i<=mid && j<=high)
    {
    	if(S[i] < S[j])
        {
        	U[k] = S[i];
            i++
        }
        else
        {	
        	U[k] = S[j];
            j++;
        }
        k++;
    }
    if(i>mid)
  		copy S[j] through S[high] to U[k] through U[high];
    else
    	copy S[j] through S[mid] to U[k] through U[high];
    copy U[low] through U[high] to S[low] through S[high];
}

2-3. 빠른 정렬

  • pseudo code
void quicksort(index low, index high)
{
	index pivotpoint;
    if(high > low)
    {
    	partition(low, high, pivotpoint);
        quicksort(low, pivotpoint-1);
        quicksort(pivotpoint+1, high);
    }
}
void partition(index low, index high, index& pivotpoint)
{
	index i, j;
    keytype pivotitem;
    pivotitem = S[low];
    j = low;
    for(i=low+1; i<=high; i++)
    {
    	if(S[i] < pivotitem)
        {
        	j++;
            exchange S[i] and S[j];
        }
    }
    pivotpoint = j;
    exchange S[low] and S[pivotpoint];
}
  • 시간 복잡도
    • partition의 경우
      • T(n) = n-1
    • quicksort의 경우 (최악) - 비내림차순 정렬된 경우
      • T(n) = T(n-1)+n-1, T(0) = 0
        -> T(n)=n(n1)2T(n)=\frac{n(n-1)}{2}
    • 평균의 경우
      • pivottiem이 p번째 데이터가 될 확률 1/n
      • A(n)=p=1n1n[A(p1)+A(np)]+n1Θ(nlg n)A(n) = \sum_{p=1}^{n}\frac{1}{n}[A(p-1)+A(n-p)]+n-1\in\Theta(nlg\ n)
    • 최고의 경우
      • 문제가 매번 반 씩 나누어질때
      • T(n)=2T(n/2)+n1Θ(nlg n)T(n) = 2T(n/2)+n-1\in\Theta(nlg\ n)

2-4. 행렬 곱셈 (쉬트라쎈 방법)

  • 단순한 곱셈의 시간복잡도
    • 곱셈을 단위 연산으로
    • T(n)=8T(n2)T(n) = 8T(\frac{n}{2}), n=2kn=2^k, T(1)=1T(1)=1
    • Θ(n3)\in \Theta(n^3)
  • 쉬트라센의 방법
    • 곱셈을 단위 연산으로
    • T(n)=7T(n2)T(n) = 7T(\frac{n}{2}), n=2kn=2^k, T(1)=1T(1)=1
    • Θ(n2.81)\in \Theta(n^{2.81})

2-5. 큰 정수 계산법

  • 단순 곱셈 : n2n^2시간

곱하는 수를 나눠서 계산

  • pseudo code
large_integer prod(large_integer u, large_integet v)
{
	large_integer x,y,w,z;
    int n,m;
    
    n = max(u의 자리, v의 자리);
    if(u==0 || v==0)
    	return 0;
    else if(n<=threshold)
    	return u*v;
    else
    {
    	m = floor(n/2);
        x = u div 10^m;
        y = u mod 10^m;
        w = v div 10^m;
        z = v mod 10^m;
    }
    return prod(x,w)*10^(2m) + (prod(x,z)+prod(w,y))*10^m + prod(y,z);
}
  • 시간 복잡도
    • 최악의 경우
    • W(n)=4W(n2)+cnW(n) = 4W(\frac{n}{2}) + cn
      -> Θ(n2)\in \Theta(n^2) : 단순 곱셈보다 좋아지지 않았음

개선된 방법

  • r = (x+y)(w+z) = xw+(xz+yw)+yz
  • p = xw
  • q = yz
large_integer prod2(large_integer u, large_integet v)
{
	large_integer x,y,w,z;
    int n,m;
    
    n = max(u의 자리, v의 자리);
    if(u==0 || v==0)
    	return 0;
    else if(n<=threshold)
    	return u*v;
    else
    {
    	m = floor(n/2);
        x = u div 10^m;
        y = u mod 10^m;
        w = v div 10^m;
        z = v mod 10^m;
        r = prod(x+y, w+z);
        p = prod(x,w);
        q = prod(y,z);
    }
    return p*10^(2m) + (r-p-q)*10^m + q;
}
  • 시간 복잡도
    • 3W(n2)+cnW(n)3W(n2+1)+cn3W(\frac{n}{2})+cn \le W(n) \le 3W(\frac{n}{2}+1)+cn
    • Θ(n1.58)\in \Theta(n^{1.58})

2-6. 도사 정리

3. Algorithm: Dynamic Programming

3-1. 이항계수 구하기

  • recursive property
    • B[i][j] = B[i-1][j-1]+B[i-1][j] (0<j<i)
    • 1 (j=0 or i=0)
  • pseudo code
int bin(int n, int k)
{
	index i, j;
    int B[0..n][0..k];
    for(i=0; i<=n; i++)
    {
    	for(j=0; j<=min(i,k); j++)
        {
        	if(j==0 || i==0)
            	B[i][j] = 0
            else
            	B[i][j] = B[i-1][j-1] + B[i-1][j];
        }
    }
    return B[n][k];
}
  • 시간 복잡도
    • 1+2+3+..+k+(k+1)+...(k+1)=k(k+1)2+(nk+1)(k+1)=(2nk+1)(k+1)2Θ(nk)1+2+3+..+k+(k+1)+...(k+1)=\frac{k(k+1)}{2}+(n-k+1)(k+1)=\frac{(2n-k+1)(k+1)}{2}\in \Theta(nk)

3-2. 최단경로 찾기

  • recursive property
    • Dk[i][j]=min(D(k1)[i][j], D(k1)[i][k]+D(k1)[k][j])D^{k}[i][j] = min(D^{(k-1)}[i][j],\ D^{(k-1)}[i][k]+D^{(k-1)}[k][j])

Floyd1

  • pseudo code
void floyd(int n, const number W[][], number D[][])
{
	int i,j,k;
    D=W;
    for(k=1; k<=n; k++)
    {
    	for(i=1; i<=n; i++)
        {
        	for(j=1; j<=n; j++)
            	D[i][j] = min(D[i][j], D[i][k]+D[k][j]);
        }
    }
}
  • 시간 복잡도
    T(n)=nnn=n3Θ(n3)T(n) = n*n*n = n^3\in\Theta(n^3)

Floyd2

  • pseudo code
void floyd2(int n, const number W[][], number D[][], index P[][])
{
	index i,j,k;
    for(i=1; i<=n; i++)
    	for(j=1; j<=n; j++)
        	P[i][j] = 0;
    D=W;
    for(k=1; k<=n; k++)
    {
    	for(i=1; i<=n; i++)
        {
        	for(j=1; j<=n; j++)
            	if(D[i][k]+D[k][j] < D[i][j])
            		P[i][j] = l;
                    D[i][j] = D[i][k] + D[k][j];
        }
    }
    
}

3-3. 연쇄 행렬 곱셈

  • recursive property
    M[i][j]=mini<=k<=j1(M[i][k]+M[k+1][j]+di1dkdj)M[i][j] = min_{i<=k<=j-1}(M[i][k]+M[k+1][j]+d_{i-1}d_kd_j)
    M[i][i]=0M[i][i] = 0
  • pseudo code
int minmult(int n, const int d[], index P[][])
{
	index i,j,k,diagonal;
    int M[1..n][1..n];
    
    for(i=1; i<=n; i++)
    	M[i][i] = 0;
    for(diagoanl = 1; diagonal<= n-1; diagonal++)
    {
    	for(i=1; i<=n-diagonal; i++)
        {
        	j=i+diagonal
            
            //k가 i보다 크고 j-1보다 작은 동안
            M[i][j] = min(M[i][k]+M[k+1][j]+d(i-1)*dk*dj); 
            P[i][j] = 최소가 되도록 하는 K;
        }
    }
    return M[1][n];
}
  • 시간 복잡도
    • k루프 j-1-i+1 = diagoanl
    • i루프 n-diagonal
    • diagonal=1n1(ndiagonal)(diagonal)=n(n1)(n+1)6Θ(n3)\sum_{diagonal = 1}^{n-1}(n-diagonal)(diagonal) = \frac{n(n-1)(n+1)}{6}\in \Theta(n^3)

3-4. 최적 이진트리

  • recursive property
    A[i][j]=mini<=k<=j(A[i][k1]+A[k+1][j]+m=ijpmA[i][j] = min_{i<=k<=j}(A[i][k-1]+A[k+1][j]+\sum_{m=i}^{j}p_m
    A[i][i]=piA[i][i] = p_i
  • pseudo code
void optsearchtree(int n, const float p[], float& minavg, index R[][])
{
	index i,j,k, diagonal;
    float A[1..n+1][0..n];
    
    for(i=1; i<=n; i++)
    {
    	A[i][i-1] = 0;
        A[i][i] = p[i];
        R[i][i] = i;
        R[i][i-1] = 0;
    }
    A[n+1][n] = 0;
    R[n+1][n] = 0;
    for(diagonal = 1; diagonal<=n-1; diagonal++)
    {
    	for(i=1; i<=n-diagonal; i++)
        {
        	j=i+diagonal;
            //k가 i보다 크고 j보다 작을 동안
            A[i][j] = min(A[i][k-1]+A[k+1][j]) + p[k];
            R[i][j] = 최소로 하는 k값;
        }
    }
    minavg = A[1][n];
}
  • 시간 복잡도
    • k루프 j-i+1 = diagonal+1
    • i루프 n-diagonal
    • diagonal=1n1(ndiagonal)(diagonal+1)=n(n1)(n4)6Θ(n3)\sum_{diagonal=1}^{n-1}(n-diagonal)(diagonal+1) = \frac{n(n-1)(n-4)}{6}\in\Theta(n^3)

3-5. DNA 서열 맞춤

  • recursive property
    opt(i,j)=min(opt(i+1,j+1)+penalty,opt(i+1,j)+2,opt(i,j+1)+2)opt(i,j) = min(opt(i+1,j+1)+penalty, opt(i+1,j)+2, opt(i,j+1)+2)

4. Algorithm: Greedy Algorithm

4-1. 최소비용신장트리

prim 알고리즘

  • pseudo code
void prim(int n, const number W[][], set_of_edges& F)
{
	index i, vnear;
    number min;
    edge e;
    index nearest[2..n];
    number distance[2..n];
    
    F=none
    for(i=2; i<=n; i++)
    {
    	for(j=2; j<=n; j++)
        {
        	distance[i] = W[1][i];
            nearest[i] = 1;
        }
    }
    repeat(n-1 times)
    {
    	min = inf;
        for(i=2; i<=n; i++)
        {
        	if(0<= distance[i]< min)
            {
            	min = distance[i];
                vnear = i;
            }
        }
        e = vnear와 nearest[vnear]를 잇는 edge;
        e를 F에 추가;
        distance[i] = -1;
        for(i=2; i<=n; i++)
        {
        	if(W[i][vnear] < distance[i])
            {
            	distance[i] = W[i][vnear];
                nearest[i] = vnear;
            }
        }
    }
}
  • 시간 복잡도 분석
    T(n)=2(n1)(n1)Θ(n2)T(n) = 2(n-1)(n-1)\in\Theta(n^2)

kruskal 알고리즘

  • pseudo code
void kruskal(int n, int m, set_of_edges E, set_of_edges& F)
{
	index i,j;
    set_pointer p,q;
    edge e;
    
    E에 속한 m개의 edge의 가중치를 기준으로 비내림차순 정렬;
    F = none;
    initial(n);
    while(F에 속한 edge의 개수가 n-1보다 작다)
    {
    	e = 아직 점검하지 않은 최소 가중치를 가지는 edge;
        (i,j) = e를 edge로 만드는 vertex의 인덱스;
        p = find(i)
        q = find(j);
        if(!equal(p,q)
        {
        	merge(p,q);
            e를 F에 추가;
        }
    }
}
  • 시간 복잡도 분석
    • edge정렬 Θ(mlg m)\Theta(mlg\ m)
    • disjoint set 초기화 Θ(n)\Theta(n)
    • 반복문
      • 최대 m번 수행
        Θ(mlg n)\Theta(mlg\ n)
    • 결론 적으로 가장 큰 항인 Θ(mlg m)\in \Theta(mlg\ m)
    • 최악의 경우
      • m=n(n1)2Θ(n2)m = \frac{n(n-1)}{2}\in \Theta(n^2)
        -> Θ(mlg m)=Θ(n2lg n)\Theta(mlg\ m) = \Theta(n^2lg\ n)

0개의 댓글