알고리즘이란?

알고리즘은 주어진 문제를 풀기 위한 단계별 지시사항들입니다.

• 알고리즘을 분석의 목적

  한 가지 문제를 푸는데 여러가지 알고리즘이 있을 수 있다. 알고리즘 분석은 시간과 공간적으로 어느 것이 가장 효율적인지 알 수 있게 해준다.

• 수행시간 분석

  문제의 크기(입력의 크기)가 증가함에 따라 처리 시간이 얼마나 증가하는지 분석

• 알고리즘 분석의 종류

  Worst case

  알고리즘이 오래 걸리는 경우

  알고리즘이 느리게 수행되도록 하는 것을 입력으로 함니다.

  Best case

  알고리즘이 제일 적은 시간이 걸리게 하는 경우

  알고리즘이 가장 빨리 수행되도록 하는 것을 입력으로 합니다.

  Average case

  입력이 무작위라고 가정

• Big-O Notation

  함수에 대해 Upper bound를 찾게 해준다.

  일반적으로 $f(n) = O(g(n))$ 으로 표현

  n의 값이 클 때, $f(n)$ 의 upper bound가 $g(n)$ 의 상수배

  $$ O(g(n))=\{f(n):n \ge n_0 \ 인\ 모든\ n에\ 대해\ 0\le f(n) \le cg(n)을 \ 만족하는 \ 양의\ 상수\ c와\ n_0가\ 존재한다.\} $$

• Omega Notation

  함수에 대해 lower bound를 찾게 해준다.

  일반적으로 $f(n) = \Omega(g(n))$ 으로 표현

  n의 값이 클 때, $f(n)$ 의 lower bound가 $g(n)$ 의 상수배

  $$ \Omega(g(n))=\{f(n):n \ge n_0 \ 인\ 모든\ n에\ 대해\ 0\le cg(n) \le f(n)을 \ 만족하는 \ 양의\ 상수\ c와\ n_0가\ 존재한다.\} $$

• $\Theta$ Notation (Tight bound)

  주어진 알고리즘의 upper bound와 lower bound가 같은지 아닌지를 결정

  알고리즘의 평균 수행 시간은 항상 upper bound와 lower bound 사이에 존재

  만약 upper bound와 lower bound이 같다면 tight bound 역시 같은 증가율을 갖는다.

  $$ \Theta(g(n))=\{f(n):n \ge n_0 \ 인\ 모든\ n에\ 대해\ 0\le c_1g(n) \le f(n) \le c_2g(n)을 \ 만족하는 \ 양의\ 상수\ c_1,c_2와\ n_0가\ 존재한다.\} $$

• 가이드라인

  루프 : 루프안의 구문들의 수행시간 곱하기 반복 횟수가 최댓값이 된다.

  중복 루프 : 전체 수행 시간은 각각의 루프의 수행시간을 곱해서 구한다.

  연속된 구문들 : 각 구문의 복잡도를 더한다.

  if-then-else : 조건문 수행 시간의 then 부분 또는 else 부분 중에 더 오래 걸리는 쪽 시간을 고려. 즉, 더한 경우이다.

  로그형 복잡도 : 어떤 알고리즘의 문제의 크기를 일부(보통은 1/2)를 줄이는데 일정한 시간이 걸린다면 $O(logn)$ 이다.