Basic

P-problem ⇒ 다항식 시간에 효율적으로 해결할 수있는 문제

NP-complete problems ⇒ 효율적인 알고리즘이 알려져 있지 않다, 정확도를 낮춰서 속도 향상하자.

선형 자료구조 Array, Stack, Queue,

비선형 자료구조 Graph, Trees, Sets(반복 X), Bags, Dictionaries

Repeated Substitution Method 점화식을 계속 풀어가서 일반식 도출

Substitution Method 한계를 추측하고 증명

The Recursion-Tree Method 점화식을 트리로 만들어서 각 노드마다 비용을 계산

마스터 방법을 사용한 점화식의 점근적 한계

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

$f(n) \;\;\; vs. \;\;\;\ n^{log_ba-e}$

• case 1 <

  If $f(n) = O(n^{log_b{a-e}})$ for some constant e > 0,

  then $𝑇(𝑛) = Θ(n^{log_b a})$

• case 2 =

  If $f(n) = Θ(n^{log_b{a}})$

  then $𝑇(𝑛) = Θ(𝑓(𝑛) lg 𝑛)$

• case 3 >

  if $f(n) = Ω(n^{log_b{a+e}})$ for some constant e > 0,

  $af(n/b) ≤ cf(n)$ for some constant c<1, and $n$ 이 충분이 클 때

  then $𝑇(𝑛) = Θ(𝑓(𝑛))$

Part 1. Brute Force and Exhaustive Search

1. Sort, Search, String Matching