• 수행 빈도 $T(n)$

• 시간복잡도

$$ f(x)=O(g(x)) \iff \exists a, c:\; f(x)\le c\cdot g(x)\quad (x \ge a) \\\ \\

f(x)=\Omega(g(x)) \iff \exists a, c:\; f(x) \ge c\cdot g(x)\quad (x\ge a) \\\ \\

f(x)=\Theta(g(x)) \iff \exists a, c_1, c_2:\; c_1\cdot g(x) \le f(x)\le c_2\cdot g(x)\quad (x\ge a)

$$

• 마스터 정리

이해를 돕기 위한 메모) 1. 에서 첫 항의 경우 재귀 트리의 리프 층이 지배적. 노드 개수가 $a^{\log n}=n^{\log a}$ 아래 설명은 엄밀하지 않고 암기용으로 간소화시킨 것이다.

$T(n)=aT(n/b)+f(n)$

1. 부분문제가 전체를 지배하는 경우. $f(n) < O(n^{\log_b a}) \Rarr T(n)=\Theta(n^{\log_b a})$
2. 부분문제와 병합과정이 동등할 경우. $f(n) = \Theta(n^{\log_b{a}} \log^k n) \Rarr T(n)=f(n) = \Theta(n^{\log_b{a}} \log^{k+1} n)$
3. 병합과정이 전체를 지배하는 경우. $f(n) > O(n^{\log_b a})\Rarr T(n)=\Theta(f(n))$

• subtract-conquer

$$ T(n)=aT(n-b)+O(n^c)\\ \Longrightarrow\ T(n)=\begin{cases} O(n^c) & a<1\\O(n^{c+1}) & a=1 \\ O(n^c\cdot a^{n/b}) & a>1 \end{cases} $$

• 계산 가능성

  모든 문제는 알고리즘으로 해결 가능한 계산문제와 무한한 시간과 계산 능력으로도 해결 불가능한 계산불가문제로 나뉜다.

  • 정지 문제. 어떤 알고리즘과 입력 파일이 주어질 때, 종료 여부를 판별 가능한가?

    거짓. pf) 귀류. 가능한 알고리즘 A의 존재를 가정하자. let Copy(i): return (i, i) let A(alg, file): alg에 file을 넣었을 때 무한 루프한다면 1, 아니라면 0을 리턴 let B(result): result가 1이면 종료. result가 0이면 무한 루프. let X(alg): B(A(Copy(alg)))

    이때 X(X)를 생각하자. Case 1) 종료된다고 가정하자. 이는 X에 X를 넣으면 무한 루프함을 의미한다. 모순. Case 2) 무한 루프한다고 가정하자. 이는 X에 X를 넣으면 종료됨을 의미한다. 모순.

    따라서 A는 존재하지 않음.

• 계산문제의 분류

  1. 탐색문제: 조건을 만족하는 해를 찾는 문제
  2. 카운팅문제: 해의 개수를 세는 문제
  3. 최적화문제: 최적의 해를 찾는 문제
  4. 결정문제: 참/거짓으로만 답하는 문제 P/NP로 구분.

• P 문제: 다항 시간 내에 해결 가능한 문제

• NP 문제: 다항 시간 내에 검증 가능한 문제