알고리즘 설계

알고리즘 바로가기

자료구조

• 컴퓨터 기억공간 내에 자료를 표현하고 조직화 하는 방법

프로그램 = 자료구조 + 알고리즘

• 자료구조에 대한 고려 없는 효율적인 알고리즘의 선택,
  또는 알고리즘에 대한 고려없는 효율적인 자료구조의 선택은 무의미 하다.

기본 자료구조 종류

• 선형 자료구조 = 배열, 연결 리스트, 스택, 큐
• 비선형 자료구조 = 트리, 그래프

알고리즘 설계 기법

• 주어진 문제, 속성, 조건 등 매우 다양
  • 일반적으로 범용의 기법은 미존재
• 대표적인 설계 방법
  • 분할정복 방법
  • 동적프로그래밍 방법
  • 욕심쟁이 방법

알고리즘 분석

정확성 분석(x)

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

효율성 분석

• 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
  • 메모리 양 -> 공간 복잡도
  • 수행시간 -> 시간복잡도 (공간복잡도 보다 중요)

시간복잡도

• 알고리즘을 프로그램으로 구현해서 이를 컴퓨터에서 실행시켜 실제 수행시간을 측정 (X 잘못됬다.)
• 알고리즘이 수행하는 기본적인 연산의 횟수의 합

점근성능

• 입력 크기 n이 무한대로 커짐에 따라 결정되는 성능
• 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현
• 알고리즘의 우열을 표현

점근성능의 표기법

• big-oh : 최악의 수행시간
• big-omega : 최선의 수행시간