-Asymptotic notation
Big-O notation (점근적 상한)(asymptotic upper bound)
f(n)의 복잡도는 최악의 경우라도 g(n) 보다 작거나 같다는 의미입니다. (f(n) ≤ g(n))
->알고리즘 성능이 최악의 경우라도 g(n) 이상이라는 의미
2. BIg-Ω notation (점근적 하한)(asymptotic lower bound)
f(n)의 복잡도는 최선의 경우라도 g(n) 보다 크거나 같다는 의미입니다. (f(n) ≥ g(n))
->알고리즘 성능이 아무리 빨라도 g(n) 이하라는 의미
3. Big-Θ notation (점근적 상한 및 하한)(asymptotic tight bound)
f(n)의 복잡도가 최선의 경우나 최악의 경우라도 g(n) 범위 내에 있다는 의미입니다. (대략 f(n) = g(n))->알고리즘 성능이 g(n)의 상한과 하한에 포함한다는 의미
O-notation and Ω-notation are like <=and >=.
o-notation and w-notation are like < and >.
점화식을 푸는 3가지 방법: substitution(치환), Recursion-tree(재귀트리), master
->점화식: 하나 이상의 base case 및 더 작은 인수가 있는 자제
1. substitution(치환): 한도를 추측한 다음 수학적 귀납법으로 통해 증명
2. Recursion-tree(재귀트리):
3. master method(마스터 정리)
-Strassen’s idea
-VLSI layout/ H-tree embedding
