程序代写代做代考 algorithm compiler C Running Time Analysis and Asymptotic Notation

Running Time Analysis and Asymptotic Notation
Running Time Analysis and Asymptotic Notation
COMP4500/7500 July 24, 2019
July 24, 2019 1/29

Running Time Analysis and Asymptotic Notation
What is an algorithm?
An algorithm is a well-defined computation procedure that takes some values as input and produces some value, or set of values, as output [CLRS CH1].
Usually defined to solve a specific computational problem.
We would like such algorithms to be correct (w.r.t. their problem) and efficient.
July 24, 2019
2/29

Running Time Analysis and Asymptotic Notation
Sorting Problem
input Asequenceofnumbersha1,a2,…,ani
output A permutation ha10 , a20 , . . . , an0 i of the input sequence such thata10 a20 …an0
July 24, 2019 3/29

Running Time Analysis and Asymptotic Notation
Sorting Algorithm: Insertion Sort
INSERTION-SORT(A)
1 2 3 4 5 6 7 8
for j = 2 to A.length key = A[j]
// Insert A[j] into the sorted sequence A[1..j 1] i=j1
whilei >0andA[i]>key
A[i + 1] = A[i]
i=i1 A[i+1]=key
Try it on A = [5,2,4,6,1,3].
July 24, 2019 4/29

Running Time Analysis and Asymptotic Notation
Sorting Algorithm: Insertion Sort
INSERTION-SORT(A)
1 2 3 4 5 6 7 8 9
for j = 2 to A.length
// Invariant: A[1..j1] contains original elements // from A[1..j1], but in sorted order
key=A[j]
// Insert A[j] into the sorted sequence A[1..j 1] i=j1
whilei >0andA[i]>key
A[i + 1] = A[i]
i=i1 A[i+1]=key
10
Loop invariants can be used to prove algorithms are correct.
July 24, 2019 5/29

Running Time Analysis and Asymptotic Notation
Execution Time
What does it depend on?
input size, e.g. sorting 10 elements versus 1000 elements
input value, e.g. sorting an already sorted list versus a reverse sorted list
Generally we want an upper bound on execution time.
July 24, 2019 6/29

Running Time Analysis and Asymptotic Notation
Execution time: Worst, Average and Best case
Definition (Worst case)
T (n) = Maximum execution time over all inputs of size n Definition (Average case)
T (n) = Average execution time over all inputs of size n, weighted by the probability of the input
Definition (Best case)
T (n) = Mimimum execution time over all inputs of size n
July 24, 2019 7/29

Running Time Analysis and Asymptotic Notation
Running Time Analysis
The running time of an algorithm on a given input can be measured in terms of the number of primitive steps executed.
July 24, 2019 8/29

Running Time Analysis and Asymptotic Notation
Sorting Algorithm: Insertion Sort
Let n be A.length.
Let’s measure time in terms of the number of array comparisons (in red):
INSERTION-SORT(A)
1 2 3 4 5 6 7 8
for j = 2 to A.length key = A[j]
// Insert A[j] into the sorted sequence A[1..j 1] i=j1
whilei >0andA[i]>key
A[i + 1] = A[i]
i=i1 A[i+1]=key
Worst case: T(n) = Pnj=2(j1) = n(n 1)/2 Bestcase:T(n)= nj=2(1)=n1
July 24, 2019 9/29
P

Running Time Analysis and Asymptotic Notation
Running Time Analysis: Recursion
More complicated than conditionals and loops.
Running time can often be described by a recurrence
Overall running time on a problem of size n is described in terms of running time(s) on smaller inputs and functions of n. (see CLRS Ch2 Ex: Merge Sort)
July 24, 2019 10/29

Running Time Analysis and Asymptotic Notation
Asymptotic Analysis: the general idea
Groups functions together based on their rate of growth. Merge sort ⇥(n lg n)
Insertion sort ⇥(n2)
For large inputs, difference in order outweigh constant factors:
E.g. Merge sort is ultimately better for large enough n no matter what the constant factors.
Ignores implementation dependent constants:
machine speed compiler
July 24, 2019
11/29

Running Time Analysis and Asymptotic Notation
Growth of functions
July 24, 2019
12/29
Largest instance that can be solved in given time
1second 1, 000, 000 62, 746 1, 000 100 2n 19
1day 86, 400, 000, 000 2, 755, 147, 514 293, 938 4, 421 36
1year 31, 536, 000, 000, 000 798, 160, 978, 500 5, 615, 692 31, 593 44
T (n) n
n log n n2 n3

Running Time Analysis and Asymptotic Notation
Asymptotic Analysis: limitations?
Constant factors are relevant for
small input sizes, and algorithms of same order
July 24, 2019
13/29

Running Time Analysis and Asymptotic Notation
Asymptotic notation
July 24, 2019
14/29
For functions f and g
f 2 O(g) f is asymptotically bounded above by g to within a constant factor
n 2 O(n2)
64, 000n 2 O(n)
f 2 ⌦(g) f is asymptotically bounded below by g to within a constant factor
g 2 O(f) n2 2 ⌦(n)
f 2 ⇥(g) f is asymptotically bounded above and below by g to within a constant factor
f 2O(g)^f 2⌦(g) 42n 2 ⇥(n)
n 62 ⇥(n2)

Running Time Analysis and Asymptotic Notation
Upper Bounds
Definition (Big-O)
O(g)={f|9c,n0 >0•8nn0 •0f(n)c.g(n)}
f 2O(g) () 9c,n0 >0•8nn0 •0f(n)c.g(n)
July 24, 2019 15/29

Running Time Analysis and Asymptotic Notation
Upper Bounds
Definition (Big-O)
O(g)={f|9c,n0 >0•8nn0 •0f(n)c.g(n)} Prove that: 2n3 2 O(n3)
Needconstantsc,n0 >0suchthat(8nn0 •02n3 cn3). Choosing c = 2 and n0 = 1 will suffice since:
8n1•02n3 2n3 ⌘ true
July 24, 2019 16/29

Running Time Analysis and Asymptotic Notation
Quick question: upper Bounds
Definition (Big-O)
O(g)={f|9c,n0 >0•8nn0 •0f(n)c.g(n)} Prove that: 2n2 2 O(n3 n2)
July 24, 2019 17/29

Running Time Analysis and Asymptotic Notation
Lower Bounds
Definition (⌦)
⌦(g)={f|9c,n0 >0•8nn0 •0c.g(n)f(n)}
f 2⌦(g) () 9c,n0 >0•8nn0 •0c.g(n)f(n)
July 24, 2019 19/29

Running Time Analysis and Asymptotic Notation
Lower Bounds
Definition (⌦)
⌦(g)={f|9c,n0 >0•8nn0 •0c.g(n)f(n)}
Prove that: 2n3 2 ⌦(n3)
Needconstantsc,n0 >0suchthat(8nn0 •0cn3 2n3). Choosing c = 2 and n0 = 1 will suffice since:
8n1•02n3 2n3 ⌘ true
July 24, 2019 20/29

Running Time Analysis and Asymptotic Notation
Tight Bounds
Definition (⇥)
⇥(g) = {f| 9c1,c2,n0 > 0 •
8nn0 •0c1.g(n)f(n)c2.g(n)}
f2⇥(g)() 9c1,c2,n0>0•
8nn0 •0c1.g(n)f(n)c2.g(n)
July 24, 2019 21/29

Running Time Analysis and Asymptotic Notation
Tight Bounds
Definition (⇥)
⇥(g) = {f| 9c1,c2,n0 > 0 •
8nn0 •0c1.g(n)f(n)c2.g(n)} Prove that: 2n3 2 ⇥(n3)
Need constants c1, c2, n0 > 0 such that (8nn0 •0c1n3 2n3 c2n3).
Choosing c1 = c2 = 2 and n0 = 1 will suffice since:
8n1•02n3 2n3 2n3 ⌘ true
July 24, 2019 22/29

Running Time Analysis and Asymptotic Notation
Tight Bounds: Prove: n2 2n 2 ⇥(n2) 2
Need constants c1, c2, n0 > 0 such that
2n2 2
(8nn0•0c1n  22nc2n).
0  c1n2 ⌘ true
ifn0 ifn>01
c1n2n2 2n 12
⌘ 2n(2c1) ⌘ 8n
ifc1=4 21
n2 2nc2n2
⌘ true ifn0andc2 2
Choosing c1 = 1 , c2 = 1 and n0 = 8 will therefore suffice. 42
July 24, 2019
23/29

Running Time Analysis and Asymptotic Notation
Properties of asymptotic notation
Theorem
f 2O(g) =) g+f 2⇥(g) Forexample,n2O(n2) =) n2+n2⇥(n2)
Theorem
Fork >0, Theorem
k.na 2 ⇥(na) Fork >0and0ab
k.na 2 O(nb)
July 24, 2019 24/29

Running Time Analysis and Asymptotic Notation
Properties of asymptotic notation
Theorem
For any functions f and g
f 2 O ( g ) () g 2 ⌦ ( f )
Theorem
For any functions f and g
f 2⇥(g) () f 2O(g)^f 2⌦(g)
July 24, 2019 25/29

Running Time Analysis and Asymptotic Notation
Comparing Functions
Definition (Asymptotically non-negative)
A function f is asymptotically non-negative if 9n0 •(8nn0 •f(n)0)
Theorem
If f and g are asymptotically non-negative functions, and limn!1f(n) =c0 then f2O(g)
g(n)
=c>0 then f2⇥(g)
=1 then g2O(f) where c is a real-valued constant.
July 24, 2019 26/29

Running Time Analysis and Asymptotic Notation
Cannot compare all functions
July 24, 2019
27/29
For example the functions
n and n1+sinn
are not comparable.

Running Time Analysis and Asymptotic Notation
Polynomials
p(n)= Theorem
Ifad >0,
Xd k 0 1 2 d
k=0
akn =a0n +a1n +a2n +···+adn p(n) 2 ⇥(nd )
lim p(n) n!1 nd
PPk = lim d ak n n!1 k=0 nd
=lim adnd +Pd1aknk n!1 nd k=0 nd
=lim a+d1ak =an!1 d k=0ndk
d
July 24, 2019 28/29

Running Time Analysis and Asymptotic Notation
Polynomials
Theorem
Fora>1andd 0,
nd 2 O(an)
lim nd n!1 an
by L’Hôpital’s rule
= =
lim dnd 1 n!1 an ln a
by L’Hôpital’s rule lim d (d 1)nd 2
n!1 an(lna)2 d times
=
=limn!1 n d! d
lim d (d 1)(d 2)…1n0 n!1 an(lna)d
=
a (lna) d as d! and (lna)
are constants and a
n
tends to 1
0
July 24, 2019 29/29