알고리즘 설계

알고리즘 설계 기법

• 주어진 문제, 속성, 조건 등의 매우 다양

  • 일반적이고 범용의 기법은 미존재

• 대표적인 설계 기법

  • 분할정복 방법
  • 동적 프로그래밍 방법
  • 욕심쟁이 방법

알고리즘 분석

알고리즘 분석

• 정확성 분석

  • 유효한 입력, 유한 시간 -> 정확한 결과 생성?
    • 다양한 수학적 기법을 사용해서 이론적 증명이 필요

• 효율성 분석

  • 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
  • 메모리 양 -> 공간 복잡도
    • 정적 공간 + 동적 공간
  • 수행시간 -> 시간 복잡도

시간 복잡도

• 알고리즘을 프로그램으로 구현해서 이를 컴퓨터에서 실행시켜 실제 수행 시간을 측정

  • 이런 방법은 일반적이지 못하다!
    • 컴퓨터 속도, 사용한 프로그래밍 언어, 프로그램 작성 방법, 컴파일러의 효율성 등에 종속적

• 알고리즘이 수행하는 기본적인 연산의 횟수의 합

  • 시간 복잡도에 영향을 미치는 요인
    • 입력으로 제공되는 데이터 크기(입력 크기)
    • 입력 데이터의 상태

• 입력 크기 n이 증가하면 수행 시간도 증가

  • 단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현

• 입력 데이터의 상태에 종속적

  • 평균 수행 시간
  • 최선 수행 시간
  • 최악 수행 시간

점근 성능

점근 성능

• 입력 크기 n이 무한대로 커짐에 따라 결정되는 성능

• 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현

  • 수행 시간의 어림값, 수행 시간의 증가 추세 파악이 용이 -> 알고리즘의 우열의 표현

점근성능의 표기법

• 정의 1 Big-oh 점근적 상한

  • 어떤 양의 상수 c와 n₀이 존재하여 모든 n>= n₀에 대하여 f(n) <= c*g(n) 이면 f(n)= O(g(n)) 이다.

• 정의 2 Big-omega 점근적 하한

  • 어떤 양의 상수 c와 n₀이 존재하여 모든 n>= n₀에 대하여 f(n) >= c*g(n) 이면 f(n)= Ω(g(n)) 이다.

• 정의 3 Big-theta 점근적 상하한

  • 어떤 양의 상수 c₁, c₂와 n₀이 존재하여 모든 n>= n₀에 대하여 c₁*g(n) <= f(n) <= c₂*g(n) 이면 f(n)= Θ(g(n)) 이다.

• 주요 O-표기 간의 연산 시간의 크기 관계

• O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

알고리즘의 시간 복잡도 구하기

• 알고리즘의 시간 복잡도를 구하려면

  • 알고리즘의 수행 시간 f(n)을 구한 후
  • f(n) = o(g(n))을 만족하는 최소 차수의 함수 g(n)을 찾음

• 실용적인 접근 방법

  • 알고리즘에 나타난 루프의 반복횟수를 조사하여 시간 복잡도로 취함
  • g(n)은 최고 차수에 의존

순환 알고리즘의 성능

순환 알고리즘의 성능

• 순환
  • 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태
  • T(n) = T(n/2) + o(1), T(1)= C₁