My Algorithms Note 演算法筆記本

方向:  與金融市場結合
--------------------


Lecture 1:

Sorting Problem

Insertion sort

Key

Running Time Analysis
1. Depending on input (eg. already sorted will be faster)
2. Depending on input size (6 elements vs. 6*10^9)
   parameterize in input size
3. Want Upper Bounds (represent a guarantee to user)

Kinds of Analysis:
1. Worst-Case Analysis (usually):
     T(n) = max time on any input  of size n
2. Average-Case(sometimes):
     T(n) = expected time over all inputs of size n
     probability to every input? We need an assumption of the statistical distribution. eg. uniform distribution.
期望值(expectation)的意義.....!!??

3. Best-case(bogus虛假)

What is insertion sorts worst-case time?
Depends on computer
  --relative speed (on same machine)
  --absolute speed (on different machine)

BIG IDEA!!!  Asymptotic Analysis

1. Ignore machine dependent constants
2. Look at growth of T(n) as n ---> infinity無限
    T(n)---> Running Time

Asymptotic Notation:

theta Θ notation: 1. Drop low-order terms
                           2. Ignore leading constants
http://en.wikipedia.org/wiki/Theta

Ex:  3 n^3 + 90 n^2 -5n + 6046    = Θ (n^3) 
          ^^            ^^^^^^^^^^^^^^^^^^^^^--->low-order terms
          ^^ Leading constant = 3

As n---> infinity,  Θ(n^2) algorithm always beats  Θ(n^3) algorithm !!!

Θ is a weak notation (descriptive notation). Not a strong notation(eg Leibniz notation in Calculus).


INSERTION-SORT.A/
1 for j D 2 to A:length
2 key D AŒj
3 // Insert AŒj into the sorted sequence AŒ1 : : j 1 .
4 i D j 1
5 while i > 0 and AŒi > key
6 AŒi C 1 D AŒi
7 i D i 1

8 AŒi C 1 D key


Insertion sort analysis:
Worst-Case : input reverse sorted

Math: Arithmetic Series 等差序列: 1+2+3+4.......n-1
Is insertion sort fast?
>> Moderately so, for small n
>> Not at all for big n.




Merge Sort: A[1,2,........]
1. if n=1, done.
2. Recursively sort
    A[1.....[n/2]]  and
    A[[n/2]+1......n]
Key subroutine(子程序): Merge