0%

Algorithm

《Introduction to Algorithms》 Notes

Asymptotic notation

How we measure a Algorithms performance on computer?

  • relative speed(on same machine)
  • absolute speed(on different machine)
  1. Ignore machine dependent constants
  2. 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

Sorting Algorithm

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(伪代码)

1. insertion sort

$\underbrace{□□□□}_{sorted}\overbrace{□}^{key}□□□□□□$

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<length;i++)
{
int key = a[i];
int j;
for(j=i-1;j>0&&a[j]>key;j--)
{
a[j+1] = a[j];
}
a[j+1] = key;
}