Analysis of Algorithms

수많은 내용이 생략됨;;

Analysis of Algorithms

---

Time Complexity of Algorithms

time complexity of an algorithm : the time it takes to execute an algorithm

 

upper bound : a best possible algorithm for solving the problem

- determining upper bound : just solve the problem

lower bound : No algorithm for solving the problem will have complexity lower than the bound

- show that time complexity of any algorithm that solves the problem is not lower than the lower bound

 

if upper bound = lower bound, time complexity of the problem has been determined

 

* must look additional content in lecture

---

Tractable and Intractable Problems

efficient algorithm : algorithm with time complexity that does not grow faster than $n^k$ (bounded by polynomial)

inefficient algorithm : algorithm with time complexity that grows faster than $n^k$

 

tractable (computationally easy) problems : problems that can be solved by efficient algorithm

intractable (computationally difficult) problems : problems that have no efficient algorithm for solving

- to show that the problem is intractable : show a lower bound of the problem grows faster than $n^k$

 

class of NP-complete problems (NP : nondeterministic polynomial)

- no efficient algorithm is currently known

- not been able to prove efficient algorithms cannot exist for their solution

- It has been shown that these problems are either all tractable($=$P) or all intractable($\neq$P)

---

Performance Analysis and Measurement

Asymptotic Notation ($O$, $\Omega$, $\Theta$)

 

upper bound $O$

- let f and g be nonnegative functions

- $f(n)=O(g(n))$ iff there exist $c$ and $n_0$ such that $f(n)\leq c\cdot g(n)$ for all $n>n_0$, $c>0$

lower bound $\Omega$

- let f and g be nonnegative functions

- $f(n)=\Omega (g(n))$ iff there exist $c$ and $n_0$ such that $f(n)\geq c\cdot g(n)$ for all $n>n_0$, $c>0$

upper and lower bound $\Theta$

- let f and g be nonnegative functions

- $f(n)=\Theta (g(n))$ iff $g(n)$ is both upper and lower bound of $f(n)$

 

some examples

---

학교 강의를 토대로 개인 공부 목적으로 작성되어 오타가 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.