[algorithm] 알고리즘의 기초

• 주어진 문제를 풀기위한 명령어들의 단계적 나열
  • 입출력
    • 0개 이상의 외부 입력 -> 1개 이상의 출력
  • 명확성
    • 각 명령은 모호하지 않고 단순 명확해야 함
  • 유한성
    • 한정된 수의 단계를 거친 후에는 반드시 종료
  • 유효성
    • 모든 명령은 컴퓨터에서 수행 가능해야함
  • 주어진 문제에 대한 결과를 생성하기위해 모호하지 않고 간단하며 컴퓨터가 수행가능한 일련의 유한개의 명령들을 순서적으로 구성한 것
  • 실용적관점
    • 효율적이어야 함
• 알고리즘 생성단계
  • 설계 -> 표현기술 -> 정확성 검증 -> 효율성 분석
• 알고리즘 표현/기술 방법
  • 일상언어
  • 의사코드
  • 순서도
• 알고리즘의 설계
  • 알고리즘(1): 값들을 하나씩 모두 비교해가면서 찾는 방법
  • 알고리즘(2): 토너먼트 방식
  • 최대값찾기에서 1번과 2번중 어떤것이 더 효율적일까?
    • 효율성을 찾는 기준은 비교의 횟수임 
    • 1번: 8개의 값을 7번 비교 n -> (n-1)
    • 2번: 8개의 값을 7번 비교 n -> (n-1)
  • 뒤섞인 카드에서 원하는 카드 찾기
    • 앞에서부터 카드를 하나씩 뒤집어 K를 찾는다 -> 순차탐색
  • 순서대로 나열된 카드에서 원하는 카드 찾기
    • 가운데를 뒤집으면서 뒤집은 값보다 큰지 작은지 확인하여 그것을 기준으로 해서 찾는다 -> 이진 탐색(binary search)
• 알고리즘 설계기법
  • 주어지는 문제, 속성, 조건 등이 매우 다양
    • 범용적인 설계기법은 미존재
  • 대표적인 알고리즘 설계 기법
    • 분할정복 방법(divide-and-conquer)
    • 동적 프로그래밍방법(dynamic programming)
    • 욕심쟁이 방법(greedy)
• 알고리즘의 분석
  • 정확성 분석
    • 유효한 입력, 유한 시간 -> 정확한 결과 생성여부?
      • 다양한 수학적 기법을 사용해서 이론적인 증명이 필요
  • 효율성 분석 
    • 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
    • 메모리 양 -> 공간 복잡도 space complexity
      • 정적 공간 + 동적 공간
    • 수행 시간 -> 시간 복잡도 time complexity
      • 구현한 알고리즘을 컴퓨터에서 실행시켜 실제 수행시간 측정하는 방법
        • 일반성 결여
          • 컴퓨터 속도, 프로그래밍 언어, 프로그램 작성방법, 컴파일러의 효율성 등에 종속적임
      • 시간 복잡도 -> 알고리즘의 단위 연산의 수행 횟수의 "합"
        • 시간 복잡도에 영향을 미치는 요인
          • 입력 크기
            • 입력으로 제공되는 데이터의 크기, 문제가 해결하려는 대상이 되는 개체의 개수
            • 예: 행렬의 크기, 리스트 원소의 수, 그래프의 정점의 수 등
          • 입력 데이터의 상태
          • 입력 크기 n이 증가하면 수행 시간도 증가
            • 단순히 수행되는 단위 연산의 개수의 합으로 표현하는 것은 부적절
              • 입력 크기 n에 대한 함수 f(n)으로 표현
          • 입력 데이터의 상태에 종속적
            • 평균 수행 시간
            • 최선 수행 시간
            • 최악 수행 시간
              • 아무리 시간이 오래걸려도 이 시간보다 더 걸릴 수 없음
  • 점근 성능
    • 입력크기 n이 무한대로 커짐에 따라 결정되는 성능
    • 점근 성능의 결정 방법
      • 수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현
        • 수행 시간의 정확한 값이 아닌 어림값
          • 수행 시간의 증가 추세를 파악하는데 용이
            • 알고리즘의 우열 표현이 용이
    • 접근성능의 표기법
      • Big-oh 점근적 상한
        • 함수 f와 g를 각각 양의 정수를 갖는 함수라 하자
          • 어떤 양의 상수 c와 n0이 존재하여 모든 n>=n0에 대하여 f(n) <= c*g(n)이면 f(n)=O(g(n))이다.
      • Big-omega 점근적 하한
        • 어떤 양의 상수 c와 n0이 존재하여 모든 n>=n0에 대하여 f(n)>=c*g(n)이면 f(n)=Ω(g(n))이다.
      • Big-theta 점근적 상하한
        • 어떤 양의 상수 c1, c2와 n0이 존재하여 모든 n>=n0에 대하여 c1*g(n)<=f(n)<=c2*g(n)이면 f(n)=Θ(g(n))이다.
      • f(n) = 3n+5, g(n)=n
        • n0=2, c=11 이면 n>=2에 대해서 3n+5<=11*n -> f(n)=O(g(n)) = O(n)
      • f(n) = O(g(n)) = O(n^3) -> 가장 낮은 차수의 함수
      • f(n) = Ω(g(n)) = Ω(n^3) -> 가장 높은 차수의 함수
      • 주요 O-표기 간의 연산 시간의 크기 관계
        • 10n+9 -> O(n) 
        • n^2/2+3n -> O(n^2)
        • 3n^3+3n+2 -> O(n^3)
        • O(1) : 상수시간 -> 가장 효율적
        • O(logn): 로그시간
        • O(n) : 선형 시간
        • O(nlogn): 로그 선형시간
        • O(n^2) : 제곱 시간
        • O(n^3): 세제곱 시간
        • O(2^n): 지수 시간 -> 가장 비효율적
    • 알고리즘의 시간 복잡도 구하기
      • 알고리즘의 시간복잡도를 구하려면
        • 알고리즘의 수행시간 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
}
// f(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[i, j] = A[i]*B[j];
// O(n^2)

• 순환 recursion, 재귀
  • 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태