Algorithmic Complexity and Probability Flashcards
What is the trade off when deciding which option for a program is the most efficient?
Time and space efficiency:
How to evaluate efficiency of programs?
- measure with a timer
- count the operations
- abstract notion of order of growth (most appropriate way)
How can you time a program?
Use a time module:
import time t0 = time.clock (start)
call function
t1 = time.clock() - t0
What are the drawbacks of timimng programs?
Timing is inconsistent:
timer varies for different inputs but cannot really express a relationship between inputs and timer
What are the positive aspects and drawbacks of counting operations?
good:
count depends on algorithm
count is independent of the computer
bad:
count depends on the implementation
no clear definition of which operation to use
Overall: count varies for different inputs and can come up with a relationship between inputs and counts
What are the problems about timing and counting as evaluation implementations?
What oyu really want to do is evaluate the algorithm, scalability and the input isze
Does the input influence how the function runs?
Yes, i.e. a function that searches for an element in a list:
1. when e is the first element in the lest –> best case
when e is not in the list –> worst case
want to measure this in a general way
(look through half for the average case)
What measure do we use to measure the order of growthß
Big OH notation
What does the big o notation measure?
The upper bound of the asymptotic growth, often called order of growth
–> big o is used to descrive worst case as it is the bottleneck when a program runs
this evaluates the algorithm and not the machine or implementation
What does O(N) measure?
–> how the time needed grows with the input growth
What types of orders of growth do we know?
Constant linear quadratic logarithmic n log n exponential
What is the law of addition for o()?
O(f(n)) + O(g(n)) = O(f(n) + g(n))
What is the law of multiplication for O()?
O8f(n)) * O(g(n)) = O(f(n) * g(n))
What complexity classes do we know and what do they mean?
O(1) –> constant running time
O(log n) –> logarithmic running time
O(n) –> denotes linear running time
O(n log n) –> denotes log-linear running time
O(nC) –> polynominial runnung rime (c constant)
O(cN) –> exponential running time (c is a constant being raised to power based on soze if input)
What are examples of constant complexity?
- -> Complexity independent of input
examples: finding length of a list in python
What are examples of linear complexity?
Simple iterative loop algorithms are typically linear in complexity?
- i.e. linear seach on unsorted list
What are examples of quadratic complexity?
determine if one list is a subset of another list
What are examples of logarithmic complexity?
complexity grows as log of size of its inputs
i.e. bisection search
What are examples of exponential complexity?
recursive functions where more than one recursive call for each size of problem
What do we use big oh for?
To compare efficiency of algorithms
- > notation that describes growth
- > lower order of growth is better
- > independent of machine specific implementation
Use big oh:
- to descrive order of growt
- upper bound
- worst case analysis
What is a sample space?
The set of all possible outcomes of a random process or experiment an event is a subset of a sample space
What is the equally likely probability formula?
S = finites sample space and E is an event in S P(E) = # of otcomes in E/ # of outcomes in S
What is the multiplication rule (probability trees)
if an operation consists of k steps and the first step can be performed in n1 ways and the second step in n2 ways …. the entire operation can be performed in n1n2…nk ways
What is a permutation?
A permutation of a set of objects is an ordering of the objects in a row. for example the set fo elements a, b, c has six permutations:
abc acb cba bca cab
How to calculate the number of permutations?
n and r are integers and 1 <= r <= n the the number of r permutations of a set of n elements r permutations
P(n, r) = n!/(n-r)!
what does
n
r n choose r denote?
The number of subsets of size r that can be chosen from a set of n elements
How do you calculate the number of subsets of size r that can be chosen from a set of n elements
n
r
n
r
= n!/ r!(n-r)!
What are the probability axioms?
For all events A and B in S: 1. 0 <= P(A) <= 1 2. P(leere menge= 0 P (S) =1 3. If A and B are disjoint then the probability of the union of A and B is P(A) + P(B)
What is the likelihood of the compliment of an event?
P(Ac) = 1- P(A)
How do you calculate the expected value of an experiment?
a1, …, an are the outcomes of the experiment and p1, …, pn are their respective probabilities:
= a1p1 + … + anpn
How do you calculate Conditional probability of B given A?
P(B|A) = P(a n B)/ P(A)
