2013年6月27日 星期四
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
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言