[알고리즘] 알고리즘 설계와 분석의 기초

정의

• 문제를 해결하는 단계적 절차 또는 방법
• 입력이 주어지고, 수행 결과를 출력
• 해야 할 작업 명확하게 명시 필요

특성

• 정확성 : 주어진 입력에 대해 올바른 해를 주어야 함
• 수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능해야 함.
• 유한성 : 알고리즘은 일정 시간 내에 종료되어야 함.
• 효율성 : 알고리즘은 효율적일수록 그 가치가 높아짐.

표현 방법

• 흐름도
• 의사코드
  • 프로그래밍 언어로 된 진짜 코드와 유사하게 표현되지만, 문법적 오류를 크게 신경 쓰지 않음
  • 언어 종속성이 없는 표현 방식

효율성

• 알고리즘의 수행 시간 또는 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기
  • 시간 복잡도
    • 실행 시간은 실행환경(하드웨어, 운영체제, 언어, 컴파일러)에 따라 달라짐
    • 실행 시간 측정 대신, 단위 연산 횟수 측정
    • 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
    • ex) 최대 숫자 찾기
      • 순차 탐색
      • 입력 : n
      • 시간복잡도 : n-1
  • 공간 복잡도

수행시간

• n에 관계 없이 일정한 시간(상수 시간)이 소요
  • 상수 시간 복잡도 O(1)
• n에 비례하는 시간 소요
  • 선형 시간 복잡도 O(n)
  • 재귀 함수
  • ex) for 루프 관련 수행 시간(p.30)
• n^2에 비례하는 시간 소요
  • ex) for 루프 nxn 반복(p.31)
• n^3에 비례하는 시간 소요
  • ex) 최대 숫자 찾기
  • es) for 루프 반복 2번 + 수행시간 n/2(p.31)

점근적 분석

• 입력의 크기가 큰 경우, 효율성이 매우 중요하다

점근적 표기법

• 입력의 크기가 무한히 커질 때, 수행시간이 증가하는 growth rate로 시간 복잡도를 표현하는 기법

Θ-표기법

• Θ[세타]
• 최고차항만 떼어내고 상수 인자(계수)제외하면 점근 적인 의미에서 같음
• 모든 n>=n0 에 대해서 c1g(n)>=f(n)>=c2g(n)이 성립하는 양의 상수c1,c2,n0이 존재하면, f(n) = ### Θ(g(n))
• 수행시간의 O-표기와 Ω-표기가 동일한 경우에 사용

O-표기법

• O[오]
• O(f(n))은 최고차항의 차수가 f(n)과 일치하거나 더 작은 함수의 집합
• 모든 n>=n0 에 대해서 f(n)<=cg(n)이 성립하는 양의 상수c 와 n0이 존재하면, f(n) ∈ O(g(n))
• n0과 같거나 큰 모든 n에 대해서 f(n)이 cg(n) 보다 크지 않다는 것
• ==g(n)을 f(n)의 상한이라고 함==

Ω-표기법

• Ω[오메가]
• Ω(f(n))은 최고차항의 차수가 f(n)과 일치하거나 더 큰 함수의 집합
• 모든 n>=n0 에 대해서 f(n)>=cg(n)이 성립하는 양의 상수c 와 n0이 존재하면, f(n) ∈ Ω(g(n))
• n0과 같거나 큰 모든 n에 대해서 f(n)이 cg(n) 보다 작지 않다는 것
• ==g(n)을 f(n)의 하한이라고 함==