FIT1008 Lecture Notes - Lecture 4: Final Solution, Combinatorial Explosion
18 Jun 2018
School
Department
Course
Professor
Running&time !"#"$!%&'$(
)$#*+
,
-*./0+1&'2&3'!"&4"$"5.+"!&61&3'7#0/"5
,
8.+*5"&.$!&%#""!&'2&0$%+5*3+0'$%&'$&7.390$"&*%"!&+'&":"3*+"'45.7
,
;07"&3'7#/":0+1 '2&./4'50+97
,
<&3'$="5+0$4&25'7'6/"7&+'&./4'50+97&+'&6"&#*+&0$+'&3'7#*+"5
Time&complexity
>0$4/"&'#&?.%%04$7"$+@2$+@&5"+*5$&"+3A&+.B"%&C&%+"#
,
D'7#.50%'$&+.B"%&C&+07"&%+"#
,
E''#%&.$!&7'!*/"%
D'7#50%"&'2&7.$1&%07#/"&'#%&.$!&+9"05&5*$$0$4&+07"
○
F"#"$!%&9'G&7.$1&+07"%&".39&'2&+9"%"&%07#/"&'#%&.5"&#"52'57"!
○
,
H*$$0$4&+07"&'2&.&%"I*"$3"&'2&%+.+"7"$+%&<&%*7&'2&5*$$0$4&+07"&'2&
%+.+"7"$+%
,
J04KL&$'+.+0'$
<&40="%&.$&0!".&'2&4?$AM%&6"9.=0'*5&2'5&/.54"&0$#*+%
N*$3+0'$&4?$A&%.0!&+'&6"&L?2?$AA&02&+9"5"&":0%+%&3'$%+.$+%&B&.$!&E&%*39&+9.+&4?$A&
O&BP2?$A&2'5&.//&$&Q&E
>0$3"&2?$A&40="%&.$&*##"5&2'*$!&+'&5*$$0$4&+07"&4?$A@
R.5+%&'2&./4'&+9.+&!'$M+&3'$+506*+"&%04$0203.$+/1&+'&5*$$0$4&+07"&3'*/!&
9.="&6""$&04$'5"!
○
J'*$!%&"55'5&7.!"&G9"$&04$'50$4&%7.//&+"57%
○
)4$'5"%&3'$%+.$+%&+''@&G9039&3'*/!&6"&/.54"&0$.3+03"
○
,
J.%03&"22030"$31&3/.%%"% ?0$&'5!"5&'2&0$35".%0$4&+07"&3'7#/":0+1A
D/.%%
J04KL&$'+.+0'$
H"7.5B%
)2&8&:S
D'$%+.$+
L?CA
H*$$0$4&+07"&!'"%$M+&!"#"$!&'$&
8&K3'$%+.$+&$*76"5&'2&'#%&
":"3*+"%
;&KKQ&;
E'4.50+9703
L?/'4$A
R5'6/"7&65'B"$&!'G$&.$!&
%'/="!&0$!"#"$!"$+/1T&
U.39&%+"#&3*+%&%0V"&61&.&3'$%+.$+&
2.3+'5T
;&KKQ&
WTXXXXXXXY;
E0$".5
L?$A
U.39&"/"7&5"I*05"%&.&20:"!&
.7'*$+&'2'3"%%0$4T
;&KKQ&S;
>*#"5/0$".5 L?$/'4$A R5'6/"7&65'B"$&!'G$&.$!&
%'/="!&0$!"#"$!"$+/1T&
U.39&%+"#&3*+%&%0V"&61&.&3'$%+.$+&
2.3+'5T
N0$./&%'/*+0'$&'6+.0$"!&61&
3'760$0$4&%'/*+0'$%T
;&KKQ&
STWWWWWWYC;
-*.!5.+03 L?$SAR5'3"%%"%&#.05%&'2&!.+.&0+"7%T
L2+"$&!*50$4&$"%+"!&/''#%T
;&KKQ&Z;
U:#'$"$+0./ L?S$AD'760$.+'50./&":#/'%0'$&?/0B"&
2.70/1&+5""A
;&KKQ&;S
N.3+'50./ L?$[A N0$!0$4&.//&#"57*+.+0'$%&'2&8&
0+"7%
K
Why&can&best&case&list&never&be&empty&list?
;07"&3'7#/":0+1&604&L&7"+9'!&.%%*7"%&/.54"&0$#*+&%0V"T&J*+&"7#+1&/0%+&9.%&%0V"&'2&
V"5'T
;9"&0$#*+&+9"'!*3"%&G'5%+K3.%"&%3"$.50'&7.1&6"&="51&*$/0B"/1&+'&'33*5,
\.1&$'+&6"&.&604&2.3+'5&0$&'="5.//&3'%+%&02'45.7&5.5"/1&*%"!,
]5'G+9&5.+"&'2&5*$$0$4&+07"&/"%%&07#'5+.$+&02'45.7&'$/1&*%"!&'$&%7.//&
0$#*+%
,
>07#/"&7049+&6"&6"++"5&+9.$&"22030"$+&^&3'7#/03.+"!&./4',
)$&$*7"503./&./4'%@&%+.60/0+1&.$!&.33*5.31&_*%+&.%&07#+&.%&"22030"$31,
`=4&3.%"&3'7#/":0+1&./G.1%&6+G$&6"%+&.$!&G'5%+&3.%"%,
Week$4:$running$time$and$time$complexity
;9*5%!.1@& CZ&a*$"&SWCb
CZ(CC
Document Summary
Nature and speed of instructions on machine used to execute program. = converting from problem to algorithm to be put into computer. Single op (assignment, print, return etc) takes 1 step. Comprise of many simple ops and their running time. Depends how many times each of these simple ops are performed. Running time of a sequence of statements = sum of running time of statements. = gives an idea of g(n)"s behaviour for large inputs. Function g(n) said to be o(f(n)) if there exists constants k and l such that g(n) Since f(n) gives an upper found to running time g(n), Parts of algo that don"t contribute significantly to running time could have been ignored. Ignores constants too, which could be large in practice. Basic efficiency classes (in order of increasing time complexity) Each elem requires a fixed amount of processing. Each step cuts size by a constant factor. Time complexity big o method assumes large input size.
