> nĳquc'fAg|lPNG
IHDR`0PLTE{tRNS#]bKGDHcmPPJCmp0712OmIDATx͎ \WޫJ^+!U|#
8`fjmuØڟ4#FiFҌ1J3bf(͈Q4#FiFҌ1J3bf(hFo4oԚxHXFC!"Ѝ$D5FAQ"D#1N0:!(xLolcBcoZFm4)qlaz8>Ԥ"4w]X-~z]'8pWG7R])١wh,#MȃJ5&7FEgGq߯>V^jΎngdH4!Lgܰz!@"Dƥ=Rcr7Q-0.DϦF߷'a%MB%!!.uHJ3ZĔj*x(ʨ&}vQjr#hR
5kE8퉿F6(2n Fgn52h4>3_vOGҌ=7ZƇLKu8F
q\7Ro~s']~t#[?7WbFFz0ESGbkQ#[#E<FFrQ2RĳadjL_'&H.~'ߘH.>_S9
ݥ1ui#3"3GR2RϏgo2yaN#f~B< Lb$َh
+7<&9H7RS :ם3ùIbުZH1gʟ·-UtX!5I{*=S&c=c`aflS"oJ1MQ\Ec}Wܿ1L,RSkB51V)PMX6T˅1?G,2P`E`4.V69֧0/1bc,2a\ă«i]/5_e߮q=
%ƍXr0SոM]S57Xh$ ִR?ؼHф7/B1E(FwKgtXx%WoЌ~fb
֬%B?,BtpXƟHota?G!YָcYzboL]G-j\Swӯՙƕ2s`ڇjWMƚBq
Z_sU[:"{vaܸ'N~ƥu4&6ƹZ8@K3N#'htSŀFo-g$nfS`qN(,s)d4~2@ƹmTo[:TE!`ogH6el#1ض+yHc
$_3IMHc%nFcVt~aFӧhᔢX[t֨uV~se%+2Ν@j:bƯ?:_lАt*0,T34&6LQ6bzk_zߗ2Qq旎zWSZ[f=UWܖ0(&}bo1tlxA献)H5:FF+]6Ǎ]L$W#d6+:\Yx~BK"d$aWY2q<\(flf-͈Q4#FiFҌ1aE3IENDB`n{ߡwיЁPNG
IHDR0
ܤsBIT&C`PLTE!!9)ޭJ91!{ZRkcKVtRNS@fbKGDIDATx횉HYC!m@t#39vD2N9^%/y'/W>OuS%,3d?wHu;',3$~%?OBvR::eVCkvԩ0 $ T"fZPv.I/g ]w]Eu pW38!)8:3eB Lѩ 4攉(;|5E(tɡؿn5ϕ\<4;لfdV9p1Ǯ4=f-EG0xpNTYԅ%kq#ƠDhFD0(0fUk#SȮQ5;`Pqa;Y[_vL0],JdPGhԵg@-pllK]xSGj$PZtlbIfqQO\sjS8-9%@ۥ!U=≆n,PJC&xA~~rmJojLd㩖dP"I0Jz2Vˉ.f`^/F3 xP@ K)x͍:,@oѫ¶#A^x\e-B(vȬvhN6갣ݠK$Wg|KZb}:QI>f褶\{VR]n-h"w®ac2ߊRWfe'"F!7#d$l=DIRcɨ
ܰ(J~/LZ*Xr4rZ5rC$AZ`>v(Y=պ_A4%]HC>=407R5bgV
Ȣ'Y3sx|b7Q#HUkȪ*!%@v9$GC.]LuVSf#
&J]m=];qON\tʄH"4(C?O2^wy/gY`4Νnnջ$|Y~H5"w(|>x,'wo}z#+t#5%5hc>"|_@ƙlD>d-bgdKBޫqDJQgY葍:6jG#2<&;GH#!-W^lG3/~O=ȁQ3о:{q1*s. 5d=)@( rT\^)ꪞ[YNk)?RgD%EZelrbU+=gpA`̪_@azmƬ6~(`ѨWx$cS&MpWl^^_*C)rFY&"-2mRm]?J#N@GoGoO= дpY#3y5(Xn?81qXU3 kSpVR;z"4+Iw1MR(t7<"ç˸>Ї9аâ)B]ȷ:ѐ蟋G?O#-@:r!Xh.
DcyoFjz#B|G*"2|c
l
xJPFel#+t"Fxfa
Gii)?J]ÆFʒ\2IENDB`.(
3/0DTimes New RomanTT4ܖ0ܖDWingdingsRomanTT4ܖ0ܖ DSimSungsRomanTT4ܖ0ܖX
B.
@n?" dd@ @@``s
+*_>7;
TX_b$ĳquc'fAg|l$$$b${ߡwיЁ0AA3@puʚ;2Nʚ;g42d2d0ppp@<4!d!d w0T<4dddd w0Tg4ddddD0@p]pp0___PPT10
___PPT9dzP?-O=$Data Structures0CSC212_Fundamental Concepts kSome fundamental concepts that you should know:
Dynamic memory allocation.
Recursion.
Performance analysis.(0<0<k `Performance Analysis 7Problems and algorithms to solve them.
Problems and problem instances.
Example: Sorting data in ascending order.
Problem: Sorting
Problem Instance: e.g. sorting data (2 3 9 5 6 8)
Algorithms: Bubble sort, Merge sort, Quick sort, Selection sort, etc.
Which is the best algorithm for the problem? How do we judge?qZZ>Z3
333,>aPerformance Analysis Two criteria are used to judge algorithms: (i) time complexity (ii) space complexity.
Space Complexity of an algorithm is the amount of memory it needs to run to completion.
Time Complexity of an algorithm is the amount of CPU time it needs to run to completion.8ZVHJ bSpace Complexity BMemory space S(P) needed by a program P, consists of two components:
A fixed part: needed for instruction space (byte code), simple variable space, constant space etc. c
A variable part: dependent on a particular instance of input and output data. Sp(instance)
S(P) = c + Sp(instance)FZZZFcP
! cSpace Complexity: Example 1 Algorithm abc (a, b, c)
{
return a+b+b*c+(a+b-c)/(a+b)+4.0;
}
For every instance 3 computer words required to store variables: a, b, and c. Therefore Sp()= 3. S(P) = 3.F?" l" ?Z&
dSpace Complexity: Example 2 cAlgorithm Sum(a[], n)
{
s:= 0.0;
for i = 1 to n do
s := s + a[i];
return s;
}d" deSpace Complexity: Example 2. Every instance needs to store array a[] & n.
Space needed to store n = 1 word.
Space needed to store a[] = n floating point words (or at least n words)
Space needed to store i and s = 2 words
Sp(n) = (n + 3). Hence S(P) = (n + 3).. ' $"K% gTime ComplexityTime required T(P) to run a program P also consists of two components:
A fixed part: compile time which is independent of the problem instance c.
A variable part: run time which depends on the problem instance tp(instance)
T(P) = c + tp(instance)
GGHA8
f Time ComplexityHow to measure T(P)?
Measure experimentally, using a stop watch
T(P) obtained in secs, msecs.
Count program steps T(P) obtained as a step count.
Fixed part is usually ignored; only the variable part tp() is measured.
.#5H.!7>Zmh
Time ComplexityWhat is a program step?
a+b+b*c+(a+b)/(a-b) one step;
comments zero steps;
while (<expr>) do step count equal to the number of times <expr> is executed.
for i=<expr> to <expr1> do step count equal to number of times <expr1> is checked.
$>:>X1KjTime Complexity: Example 1kTime Complexity: Example 2l
Performance MeasurementWhich is better?
T(P1) = (n+1) or T(P2) = (n2 + 5).
T(P1) = log (n2 + 1)/n! or T(P2) = nn(nlogn)/n2.
Complex step count functions are difficult to compare.
For comparing, rate of growth of time and space complexity functions is easy and sufficient.ZUZZ 73_mBig O NotationBig O of a function gives us rate of growth of the step count function f(n), in terms of a simple function g(n), which is easy to compare.
Definition: [Big O] The function f(n) = O(g(n)) (big oh of g of n) iff there exist positive constants c and n0 such that f(n) <= c*g(n) for all n, n>=n0. See graph on next slide.
Example: 3n+2 = O(n) because 3n+2 <= 4n for all n >= 2. c = 4, n0 = 2.I
#@
[
pBig O NotationnBig O NotationExample: 10n2+4n+2 = O(n2) because 10n2+4n+2 <= 11n2 for all n >=5.
Example: 6*2n+n2 = O(2n) because 6*2n+n2 <=7*2n for all n>=4.
Algorithms can be: O(1) constant; O(log n) logrithmic; O(nlogn); O(n) linear; O(n2) quadratic; O(n3) cubic; O(2n) exponential.Z
'>,
HoBig O NotationNow it is easy to compare time or space complexities of algorithms. Which algorithm complexity is better?
T(P1) = O(n) or T(P2) = O(n2)
T(P1) = O(1) or T(P2) = O(log n)
T(P1) = O(2n) or T(P2) = O(n10)pj _ j./ 0` ` ̙33` 333MMM` ff3333f` f` f` 3>?" dd@,|?" dd@ " @ ` n?" dd@ @@``PR @ ` `p>>VN(
6h P
T Click to edit Master title style!
!
0Hq
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
0| ``
>*
0< `
@*
00 `
@*x
BApaint" `H
0h ? ̙33 Default Design
0P,(
N-ii P#
r* H$$HHkk
NTii #
t* H$$HHkkd
c$ ?:
8
NWii
@
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
T
s*1
?
@ ZB
?
s*1
?
p@pZB
@
s*1
?
@ZB
A
s*1
?
@
ZB
B
s*o
?0B
B`B
C
0o
?B0B`B
D
0o
?
B@Bd 0O
W#"
`0O
Q
<<?0O
P2nm+2n+2 @``B
R
0o
?00`B
S
0o
?OO`B
T
0o
?0O`B
U
0o
?0OH
0h ? ̙33
0 $(
r
S)P
r
S
H
0h ? ̙33
00$(
r
SP
r
SX
H
0h ? ̙33
0~v`(
r
SP
\8 0P
0P\
C,AbigOGraph0P
<@+
*
<= n0H
0h ? ̙33
0@$(
r
S ړP
r
Sړ
H
0h ? ̙33
0P$(
r
SP
r
St
H
0h ? ̙33
0@,(
^
S:
c${
@
" H
0h9 ? ̙33rt0.CD7 h3>_/FHJKMOQUSWjpYη|Lp1)/(
3/0DTimes New RomanTT4ܖ0ܖDWingdingsRomanTT4ܖ0ܖ DSimSungsRoOh+'0T`h
4Human-Machine Interaction and User-Interface DesignInayatinayat67Microsoft PowerPoint@f.@ W@~>ro>GSg )' """)))UUUMMMBBB999|PP3f333f3333f3ffffff3f̙3ff333f333333333f33333333f33f3ff3f3f3f3333f33̙33333f333333f3333f3ffffff3f33ff3f3f3f3fff3ffffffffff3ffff̙fff3fffff3fff333f3f3ff3ff33f̙̙3̙ff̙̙̙3f̙3f333f3333f3ffffff3f̙3f3f3f333f3333f3ffffff3f̙3f3ffffffffff!___wwwff4'A x(xKʦ""")))UUUMMMBBB999|PP3f3333f333ff3fffff3f3f̙f3333f3333333333f3333333f3f33ff3f3f3f3333f3333333f3̙33333f333ff3ffffff3f33f3ff3f3f3ffff3fffffffff3fffffff3f̙ffff3ff333f3ff33fff33f3ff̙3f3f3333f333ff3fffff̙̙3̙f̙̙̙3f̙3f3f3333f333ff3fffff3f3f̙3ffffffffff!___wwwýÚýÚÚzzÚýýýýýýÚÚÚÚzzzzzzzYzzzzzzzzzàààààÚààzYzzzYzYYYYY^YYYYYYYYYYYYYYYzYYYYYYYYYYSYYYYYYY8YYY8Y8Y8YYY8YYY8YYYYYYYY^YYYYYzzzzzYzzzYYzYzYYzYYYYYzYYYYYYYYYXYYYYYYYXYYYYYYYXYYYXYYY1YYY1YYY1Y7Y1YYY1Y1Y1Y1Y1Y2Y1Y8Y8Y8Y8YYYYYYYXYYYYYYzYzzyzzàzzzzzzzzYzYYYY^YYYYYYYzYYYYY^YYYY^YY^YYYYYYYY^YYYYYYYYYYYYYYYYYY8YYYYYYYYzzzzzzzÚÚýÚýÚÚÚÚÚÚÚÚýÚÚÚzzzzzzzzXzzzzzzzzzzzzzyzzzXzzzyzzz@@``s
+*_>7;
TX_b$ĳquc'fAg|l$$$b${ߡwיЁ0AA3@puʚ;2Nʚ;g42d2d0ppp@<4!d!d w0T<4dddd w0Tg4ddddD0@p]pp0___PPT10
___PPT9dzP?-O=S%Data Structures0CSC212_Fundamental Concepts kSome fundamental concepts that you should know:
Dynamic memory allocation.
Recursion.
Performance analysis.(0<0<k `Performance Analysis 7Problems and algorithms to solve them.
Problems and problem instances.
Example: Sorting data in ascending order.
Problem: Sorting
Problem Instance: e.g. sorting data (2 3 9 5 6 8)
Algorithms: Bubble sort, Merge sort, Quick sort, Selection sort, etc.
Which is the best algorithm for the problem? How do we judge?qZZ>Z3
333,>aPerformance Analysis Two criteria are used to judge algorithms: (i) time complexity (ii) space complexity.
Space Complexity of an algorithm is the amount of memory it needs to run to completion.
Time Complexity of an algorithm is the amount of CPU time it needs to run to completion.8ZVHJ bSpace Complexity BMemory space S(P) needed by a program P, consists of two components:
A fixed part: needed for instruction space (byte code), simple variable space, constant space etc. c
A variable part: dependent on a particular instance of input and output data. Sp(instance)
S(P) = c + Sp(instance)FZZZFcP
! cSpace Complexity: Example 1 Algorithm abc (a, b, c)
{
return a+b+b*c+(a+b-c)/(a+b)+4.0;
}
For every instance 3 computer words required to store variables: a, b, and c. Therefore Sp()= 3. S(P) = 3.F?" l" ?Z&
dSpace Complexity: Example 2 cAlgorithm Sum(a[], n)
{
s:= 0.0;
for i = 1 to n do
s := s + a[i];
return s;
}d" deSpace Complexity: Example 2. Every instance needs to store array a[] & n.
Space needed to store n = 1 word.
Space needed to store a[] = n floating point words (or at least n words)
Space needed to store i and s = 2 words
Sp(n) = (n + 3). Hence S(P) = (n + 3).. ' $"K% gTime ComplexityTime required T(P) to run a program P also consists of two components:
A fixed part: compile time which is independent of the problem instance c.
A variable part: run time which depends on the problem instance tp(instance)
T(P) = c + tp(instance)
GGHA8
f Time ComplexityHow to measure T(P)?
Measure experimentally, using a stop watch
T(P) obtained in secs, msecs.
Count program steps T(P) obtained as a step count.
Fixed part is usually ignored; only the variable part tp() is measured.
.#5H.!7>Zmh
Time ComplexityWhat is a program step?
a+b+b*c+(a+b)/(a-b) one step;
comments zero steps;
while (<expr>) do step count equal to the number of times <expr> is executed.
for i=<expr> to <expr1> do step count equal to number of times <expr1> is checked.
$>:>X1KjTime Complexity: Example 1kTime Complexity: Example 2l
Perfo
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklnopqrstuvwxyz{|}~Root EntrydO)2PicturesCurrent User/SummaryInformation(mT
PowerPoint Document( DocumentSummaryInformation8MsoDataStore22OSUIORV0Q==2
22manTT4ܖ0ܖX
B.
@n?" dd@ @@``s
+*_>7;
TX_b$ĳquc'fAg|l$$$b${ߡwיЁ0AA3@puʚ;2Nʚ;g42d2d0ppp@<4!d!d w0T<4dddd w0Tg4ddddD0@p]pp0___PPT10
___PPT9dzP?-O=S%Data Structures0CSC212_Fundamental Concepts kSome fundamental concepts that you should know:
Dynamic memory allocation.
Recursion.
Performance analysis.(0<0<k `Performance Analysis 7Problems and algorithms to solve them.
Problems and problem instances.
Example: Sorting data in ascending order.
Problem: Sorting
Problem Instance: e.g. sorting data (2 3 9 5 6 8)
Algorithms: Bubble sort, Merge sort, Quick sort, Selection sort, etc.
Which is the best algorithm for the problem? How do we judge?qZZ>Z3
333,>aPerformance Analysis Two criteria are used to judge algorithms: (i) time complexity (ii) space complexity.
Space Complexity of an algorithm is the amount of memory it needs to run to completion.
Time Complexity of an algorithm is the amount of CPU time it needs to run to completion.8ZVHJ bSpace Complexity BMemory space S(P) needed by a program P, consists of two components:
A fixed part: needed for instruction space (byte code), simple variable space, constant space etc. c
A variable part: dependent on a particular instance of input and output data. Sp(instance)
S(P) = c + Sp(instance)FZZZFcP
! cSpace Complexity: Example 1 Algorithm abc (a, b, c)
{
return a+b+b*c+(a+b-c)/(a+b)+4.0;
}
For every instance 3 computer words required to store variables: a, b, and c. Therefore Sp()= 3. S(P) = 3.F?" l" ?Z&
dSpace Complexity: Example 2 cAlgorithm Sum(a[], n)
{
s:= 0.0;
for i = 1 to n do
s := s + a[i];
return s;
}d" deSpace Complexity: Example 2. Every instance needs to store array a[] & n.
Space needed to store n = 1 word.
Space needed to store a[] = n floating point words (or at least n words)
Space needed to store i and s = 2 words
Sp(n) = (n + 3). Hence S(P) = (n + 3).. ' $"K% gTime ComplexityTime required T(P) to run a program P also consists of two components:
A fixed part: compile time which is independent of the problem instance c.
A variable part: run time which depends on the problem instance tp(instance)
T(P) = c + tp(instance)
GGHA8
f Time ComplexityHow to measure T(P)?
Measure experimentally, using a stop watch
T(P) obtained in secs, msecs.
Count program steps T(P) obtained as a step count.
Fixed part is usually ignored; only the variable part tp() is measured.
.#5H.!7>Zmh
Time ComplexityWhat is a program step?
a+b+b*c+(a+b)/(a-b) one step;
comments zero steps;
while (<expr>) do step count equal to the number of times <expr> is executed.
for i=<expr> to <expr1> do step count equal to number of times <expr1> is checked.
$>:>X1KjTime Complexity: Example 1kTime Complexity: Example 2l
Performance MeasurementWhich is better?
T(P1) = (n+1) or T(P2) = (n2 + 5).
T(P1) = log (n2 + 1)/n! or T(P2) = nn(nlogn)/n2.
Complex step count functions are difficult to compare.
For comparing, rate of growth of time and space complexity functions is easy and sufficient.ZUZZ 73_mBig O Notation@Big O of a function gives us rate of growth of the step count function f(n), in terms of a simple function g(n), which is easy to compare.
Definition: [Big O] The function f(n) = O(g(n)) (big oh of g of n) iff there exist positive constants c and n0 such that f(n) <= c*g(n) for all n, n>=n0. See graph on next slide.
Example: f(n) = 3n+2 is O(n) because 3n+2 <= 4n for all n >= 2. c = 4, n0 = 2. Here g(n) = n.I
#@
c
>vHpBig O NotationnBig O Notation6Example: f(n) = 10n2+4n+2 is O(n2) because 10n2+4n+2 <= 11n2 for all n >=5.
Example: f(n) = 6*2n+n2 is O(2n) because 6*2n+n2 <=7*2n for all n>=4.
Algorithms can be: O(1) constant; O(log n) logrithmic; O(nlogn); O(n) linear; O(n2) quadratic; O(n3) cubic; O(2n) exponential.Z
#
'>P Ii
HoBig O NotationNow it is easy to compare time or space complexities of algorithms. Which algorithm complexity is better?
T(P1) = O(n) or T(P2) = O(n2)
T(P1) = O(1) or T(P2) = O(log n)
T(P1) = O(2n) or T(P2) = O(n10)pj _ j./
00$(
r
SP
r
SX
H
0h ? ̙33
0@$(
r
S ړP
r
Sړ
H
0h ? ̙33rm p1)/(
3/0DTimes New RomanTT4ܖ0ܖDWingdingsRomanTT4ܖ0ܖ DSimSungsRomanTT4ܖ0ܖX
B.
@n?" dd@
՜.+,0|
On-screen Showksu Times New Roman
WingdingsSimSunDefault DesignData StructuresFundamental ConceptsPerformance AnalysisPerformance AnalysisSpace ComplexitySpac
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFHIJLMNPQRrmance MeasurementWhich is better?
T(P1) = (n+1) or T(P2) = (n2 + 5).
T(P1) = log (n2 + 1)/n! or T(P2) = nn(nlogn)/n2.
Complex step count functions are difficult to compare.
For comparing, rate of growth of time and space complexity functions is easy and sufficient.ZUZZ 73_mBig O Notation@Big O of a function gives us rate of growth of the step count function f(n), in terms of a simple function g(n), which is easy to compare.
Definition: [Big O] The function f(n) = O(g(n)) (big oh of g of n) iff there exist positive constants c and n0 such that f(n) <= c*g(n) for all n, n>=n0. See graph on next slide.
Example: f(n) = 3n+2 is O(n) because 3n+2 <= 4n for all n >= 2. c = 4, n0 = 2. Here g(n) = n.I
#@
c
>vHpBig O NotationnBig O Notation6Example: f(n) = 10n2+4n+2 is O(n2) because 10n2+4n+2 <= 11n2 for all n >=5.
Example: f(n) = 6*2n+n2 is O(2n) because 6*2n+n2 <=7*2n for all n>=4.
Algorithms can be: O(1) constant; O(log n) logrithmic; O(nlogn); O(n) linear; O(n2) quadratic; O(n3) cubic; O(2n) exponential.Z
#
'>P Ii
HoBig O NotationNow it is easy to compare time or space complexities of algorithms. Which algorithm complexity is better?
T(P1) = O(n) or T(P2) = O(n2)
T(P1) = O(1) or T(P2) = O(log n)
T(P1) = O(2n) or T(P2) = O(n10)pj _ j./ r5f%p13(
3/0DTimes New RomanTTܖ0ܖDWingdingsRomanTTܖ0ܖ DSimSungsRomanTTܖ0ܖX
B.
@n?" dd@ @@``t
+*_>7;
TX_b$ĳquc'fAg|l$$$b${ߡwיЁ0AA3@puʚ;2Nʚ;g42d2d&0|ppp@<4!d!d w0T<4dddd w0Tg4ddddL0@p]pp0___PPT10
___PPT9dzP?-O=*Data Structures0CSC212_Fundamental Concepts kSome fundamental concepts that you should know:
Dynamic memory allocation.
Recursion.
Performance analysis.(0<0<k `Performance Analysis 7Problems and algorithms to solve them.
Problems and problem instances.
Example: Sorting data in ascending order.
Problem: Sorting
Problem Instance: e.g. sorting data (2 3 9 5 6 8)
Algorithms: Bubble sort, Merge sort, Quick sort, Selection sort, etc.
Which is the best algorithm for the problem? How do we judge?qZZ>Z3
333,>aPerformance Analysis Two criteria are used to judge algorithms: (i) time complexity (ii) space complexity.
Space Complexity of an algorithm is the amount of memory it needs to run to completion.
Time Complexity of an algorithm is the amount of CPU time it needs to run to completion.8ZVHJ bSpace Complexity BMemory space S(P) needed by a program P, consists of two components:
A fixed part: needed for instruction space (byte code), simple variable space, constant space etc. c
A variable part: dependent on a particular instance of input and output data. Sp(instance)
S(P) = c + Sp(instance)FZZZFcP
! cSpace Complexity: Example 1 Algorithm abc (a, b, c)
{
return a+b+b*c+(a+b-c)/(a+b)+4.0;
}
For every instance 3 computer words required to store variables: a, b, and c. Therefore Sp()= 3. S(P) = 3.F?" l" ?Z&
dSpace Complexity: Example 2 cAlgorithm Sum(a[], n)
{
s:= 0.0;
for i = 1 to n do
s := s + a[i];
return s;
}d" deSpace Complexity: Example 2. Every instance needs to store array a[] & n.
Space needed to store n = 1 word.
Space needed to store a[] = n floating point words (or at least n words)
Space needed to store i and s = 2 words
Sp(n) = (n + 3). Hence S(P) = (n + 3).. ' $"K% gTime ComplexityTime required T(P) to run a program P also consists of two components:
A fixed part: compile time which is independent of the problem instance c.
A variable part: run time which depends on the problem instance tp(instance)
T(P) = c + tp(instance)
GGHA8
f Time ComplexityHow to measure T(P)?
Measure experimentally, using a stop watch
T(P) obtained in secs, msecs.
Count program steps T(P) obtained as a step count.
Fixed part is usually ignored; only the variable part tp() is measured.
.#5H.!7>Zmh
Time ComplexityWhat is a program step?
a+b+b*c+(a+b)/(a-b) one step;
comments zero steps;
while (<expr>) do step count equal to the number of times <expr> is executed.
for i=<expr> to <expr1> do step count equal to number of times <expr1> is checked.
$>:>X1KjTime Complexity: Example 1kTime Complexity: Example 2l
Performance MeasurementWhich is better?
T(P1) = (n+1) or T(P2) = (n2 + 5).
T(P1) = log (n2 + 1)/n! or T(P2) = nn(nlogn)/n2.
Complex step count functions are difficult to compare.
For comparing, rate of growth of time and space complexity functions is easy and sufficient.ZUZZ 73_mBig O Notation@Big O of a function gives us rate of growth of the step count function f(n), in terms of a simple function g(n), which is easy to compare.
Definition: [Big O] The function f(n) = O(g(n)) (big oh of g of n) iff there exist positive constants c and n0 such that f(n) <= c*g(n) for all n, n>=n0. See graph on next slide.
Example: f(n) = 3n+2 is O(n) because 3n+2 <= 4n for all n >= 2. c = 4, n0 = 2. Here g(n) = n.I
#@
c
>vHpBig O NotationnBig O Notation6Example: f(n) = 10n2+4n+2 is O(n2) because 10n2+4n+2 <= 11n2 for all n >=5.
Example: f(n) = 6*2n+n2 is O(2n) because 6*2n+n2 <=7*2n for all n>=4.
Algorithms can be: O(1) constant; O(log n) logrithmic; O(nlogn); O(n) linear; O(n2) quadratic; O(n3) cubic; O(2n) exponential.Z
#
'>P Ii
HoBig O NotationNow it is easy to compare time or space complexities of algorithms. Which algorithm complexity is better?
T(P1) = O(n) or T(P2) = O(n2)
T(P1) = O(1) or T(P2) = O(log n)
T(P1) = O(2n) or T(P2) = O(n10)pj _ j.qSome Results Sum of two functions: If f(n) = f1(n) + f2(n), and f1(n) is O(g1(n)) and f2(n) is O(g2(n)), then f(n) = O(max(|g1(n)|, |g2(n)|)).
Product of two functions: If f(n) = f1(n)* f2(n), and f1(n) is O(g1(n)) and f2(n) is O(g2(n)), then f(n) = O(g1(n)* g2(n)).
\F>E / $
0p$(
r
SP
r
S
H
0h ? ̙3380___PPT10.=`*r%qYv%[q13(
3/0DTimes New RomanTT
ܖ0ܖDWingdingsRomanTT
ܖ0ܖ DSimSungsRomanTT
ܖ0ܖX
B.
@n?" dd@ @@``t
+*_>7;
TX_b$ĳquc'fAg|l$$$b${ߡwיЁ0AA3@puʚ;2Nʚ;g42d2d\0ppp@<4!d!d w0T
<4dddd w0T
g4dddd@0@p]pp0___PPT10
___PPT9dzP?-O=*Data Structures0CSC212_Fundamental Concepts kSome fundamental concepts that you should know:
Dynamic memory allocation.
Recursion.
Performance analysis.(0<0<k `Performance Analysis AThere are problems and algorithms to solve them.
Problems and problem instances.
Example: Sorting data in ascending order.
Problem: Sorting
Problem Instance: e.g. sorting data (2 3 9 5 6 8)
Algorithms: Bubble sort, Merge sort, Quick sort, Selection sort, etc.
Which is the best algorithm for the problem? How do we judge?{ZZ>Z 3
333,>aPerformance Analysis Two criteria are used to judge algorithms: (i) time complexity (ii) space complexity.
Space Complexity of an algorithm is the amount of memory it needs to run to completion.
Time Complexity of an algorithm is the amount of CPU time it needs to run to completion.8ZVHJ bSpace Complexity BMemory space S(P) needed by a program P, consists of two components:
A fixed part: needed for instruction space (byte code), simple variable space, constant space etc. c
A variable part: dependent on a particular instance of input and output data. Sp(instance)
S(P) = c + Sp(instance)FZZZFcP
! cSpace Complexity: Example 1 Algorithm abc (a, b, c)
{
return a+b+b*c+(a+b-c)/(a+b)+4.0;
}
For every instance 3 computer words required to store variables: a, b, and c. Therefore Sp()= 3. S(P) = 3.F?" l" ?Z&
dSpace Complexity: Example 2 cAlgorithm Sum(a[], n)
{
s:= 0.0;
for i = 1 to n do
s := s + a[i];
return s;
}d" deSpace Complexity: Example 2. Every instance needs to store array a[] & n.
Space needed to store n = 1 word.
Space needed to store a[] = n floating point words (or at least n words)
Space needed to store i and s = 2 words
Sp(n) = (n + 3). Hence S(P) = (n + 3).. ' $"K% gTime ComplexityTime required T(P) to run a program P also consists of two components:
A fixed part: compile time which is independent of the problem instance c.
A variable part: run time which depends on the problem instance tp(instance)
T(P) = c + tp(instance)
GGHA8
f Time ComplexityHow to measure T(P)?
Measure experimentally, using a stop watch
T(P) obtained in secs, msecs.
Count program steps T(P) obtained as a step count.
Fixed part is usually ignored; only the variable part tp() is measured.
.#5H.!7>Zmh
Time ComplexityWhat is a program step?
a+b+b*c+(a+b)/(a-b) one step;
comments zero steps;
while (<expr>) do step count equal to the number of times <expr> is executed.
for i=<expr> to <expr1> do step count equal to number e Complexity: Example 1Space Complexity: Example 2Space Complexity: Example 2.Time ComplexityTime ComplexityTime ComplexityTime Complexity: Example 1Time Complexity: Example 2Performance MeasurementBig O NotationBig O NotationBig O NotationBig O Notation
Some ResultsFonts UsedDesign Template
Slide Titles_ahmadahmaddrjof times <expr1> is checked.
$>:>X1KjTime Complexity: Example 1kTime Complexity: Example 2l
Performance MeasurementWhich is better?
T(P1) = (n+1) or T(P2) = (n2 + 5).
T(P1) = log (n2 + 1)/n! or T(P2) = nn(nlogn)/n2.
Complex step count functions are difficult to compare.
For comparing, rate of growth of time and space complexity functions is easy and sufficient.ZUZZ 73_mBig O Notation@Big O of a function gives us rate of growth of the step count function f(n), in terms of a simple function g(n), which is easy to compare.
Definition: [Big O] The function f(n) = O(g(n)) (big oh of g of n) iff there exist positive constants c and n0 such that f(n) <= c*g(n) for all n, n>=n0. See graph on next slide.
Example: f(n) = 3n+2 is O(n) because 3n+2 <= 4n for all n >= 2. c = 4, n0 = 2. Here g(n) = n.I
#@
c
>vHpBig O NotationnBig O Notation6Example: f(n) = 10n2+4n+2 is O(n2) because 10n2+4n+2 <= 11n2 for all n >=5.
Example: f(n) = 6*2n+n2 is O(2n) because 6*2n+n2 <=7*2n for all n>=4.
Algorithms can be: O(1) constant; O(log n) logrithmic; O(nlogn); O(n) linear; O(n2) quadratic; O(n3) cubic; O(2n) exponential.Z
#
'>P Ii
HoBig O NotationNow it is easy to compare time or space complexities of algorithms. Which algorithm complexity is better?
T(P1) = O(n) or T(P2) = O(n2)
T(P1) = O(1) or T(P2) = O(log n)
T(P1) = O(2n) or T(P2) = O(n10)pj _ j.qSome Results Sum of two functions: If f(n) = f1(n) + f2(n), and f1(n) is O(g1(n)) and f2(n) is O(g2(n)), then f(n) = O(max(|g1(n)|, |g2(n)|)).
Product of two functions: If f(n) = f1(n)* f2(n), and f1(n) is O(g1(n)) and f2(n) is O(g2(n)), then f(n) = O(g1(n)* g2(n)).
\F>E /
0p$(
r
SA#P
#
r
SA##
H
0h ? ̙33r[`[q1Item
PropertiesGJTUYULSBUS4EXRY==222Item
KPropertiesO
This value indicates the number of saves or revisions. The application is responsible for updating this value after each revision.
DocumentLibraryFormDocumentLibraryFormDocumentLibraryForm
~~