2강 알고리즘의 기초

알고리즘 정의

주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한 개의 명령들을 순서적으로 구성한 것
→ 효율적이여야 한다.

알고리즘의 설계

• 알고리즘의 설계 기법은 주어진 문제, 속성, 조건 등에 따라 매우 다양하다. → 범용적인 설계 기법은 존재 하지 않는다.
• 대표적인 알고리즘 설계기법
  분할정복 방법
  동적 프로그래밍 방법
  욕심쟁이 방법

알고리즘의 분석

• 정확성 분석
  유효한 입력, 유한 시간에 따른 정확한 결과 생성 여부를 분석한다
  → 다양한 수학적 기법을 사용해서 이론적인 증명이 필요하지만 수업에서 다루는 내용은 이미 증명이 된 알고리즘으로 효율성에 기반하여 분석한다!

• 효율성 분석
  알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
  메모리 양 → 공간 복잡도
  수행시간 → 시간 복잡도
• 시간 복잡도
  알고리즘의 단위 연산의 수행 횟수의 합으로 구한다. 시간 복잡도에는 입력 크기, 입력 데이터의 상태가 영향을 미친다.
  입력크기 n이 증가하면 수행 시간도 증가한다. → 입력크기 n에 대한 함수 f(n)으로 표현한다.
  입력 데이터의 상태에 종속적이기 때문에 최악 수행 시간으로 계산한다.

점근성능

• 입력 크기 n이 무한대로 커짐에 따라 결정되는 성능(알고리즘 설계는 데이터가 무한대로 있다는 가정하에 설계한다.)

• 수행 시간의 함수에서 최고차항만을 계수 없이 표현한다.
  → 수행 시간의 증가 추세를 파악하는데에 용이하기 때문이다.
  → 알고리즘의 우열을 따지기에 좋은 방법이다.

• 점근성능의 표기법
  1. 빅오 표기법 → 최악 수행시간 f(n) ≤ cg(n)
  2. 빅오메가 → 최선의 수행시간 cg(n) ≤ f(n)
  3. 빅세타 cg(n) ≤ f(n) ≤ cg(n)
• 빅오함수들의 연산 크기
  O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2**n)
• 실용적인 점근성능 구하는 방법
  알고리즘에서의 루프 횟수를 구하여 바로 구할 수 있다.

순환(재귀)

• 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태
• 시간복잡도를 구하기 어려워 점화식으로 구한다.