Computational Complexity
No description yet. This curated deck is ready for daily study.
Card preview (24)
Understand efficiency of programs
Separate time and space efficiency of a program
Challenges
• a program can be implemented in many different ways • solve a problem using only a handful of different algorithms • separate choices of implementation from abstract algorithms
Evaluate efficiency
• use a timer • count operations • abstract notion of order of growth
Timing a program
• start clock • call function • stop clock
Timing programs is inconsistent
GOAL to evaluate diff. algorithms
Running time -(time varies for different inputs, but cannot really express a relationship between inputs and time!)
+ varies between algorithms • varies between implementations • varies between computers • not predictable based on small inputs
Which operations to count
Assumes steps take constant time • mathematical operation • comparisons • assignments • accessing objects in memory
Counting operations, better but…
GOAL to evaluate different algorithms
Counting operations +(count varies for diff. inputs and can come up with a relationship between inputs and the count)
+ depends on algorithm - depends on implementation - independent of computers + no real def. of which operations to count
Needs a better way what we HAVE
• timing and counting evaluate implementations * timing evaluates machines
what we WANT
• evaluate algorithm • evaluate scalability • evaluate in terms of input size
Need to which input to use
• efficiency in terms of input • could be an integer • could be length of list • you decide
Different inputs
• first element in a list -> BEST CASE • not in list -> WORST CASE • look through half -> AVG CASE
Best case
min. running time - constant - first element of any list
Average case
avg. running time - practical measure
Worst case
max. running time - linear in length of list - must search entire list
Orders of Growth - goal
• input is very big • growth of program’s run time • upper bound • do not need to be precise “order of” not “exact” • largest factor
Input is very big
Want to evaluate programs efficiency when input is very big
Growth of program’s run time
Want to express program’s run time as input grows
Upper bound
Want to put an upper bound on growth
“order of” not “exact”
Do not need to be precise “order of” not “exact” growth
Largest factor
We will look at largest factor in run time
Types of orders of growth
- constant \+ linear - quadratic - logarithmic \+ n log n - exponential
Measuring Order of Growth
Big Oh Notation