How we measure a Algorithms performance on computer?
- relative speed(on same machine)
- absolute speed(on different machine)
- Ignore machine dependent constants
- Look at growth of T(n) as $n \rightarrow \infty$
so we need introduce the asymptotic notation to understand performance of algorithm
- $\theta $ notation is pretty easy to master because all you do is from a formula,just drop low order terms and ignore leading constants . for example , here is a formula like: $f(x)=3n^3+90n^2+6064$ well,we drop low terms and left $n^3$ ,so $\theta(f(x))=\theta(n^3)$
- O notation
- $\Omega$ notation
We have sequence $a_1$ ,$a_2$ up to $a_n$ of numbers as input, and our output is a permutation of those numbers.
such that $a_1 \leq a_2 \leq a_3 \leq … \leq a_n$
we will write those algorithm in what we call pseudocode(伪代码)