Transcript g(n)
MATEMATIK 4 INDUKTION OG REKURSION MM 1.5 MM 1.5: Kompleksitet Topics: Computational complexity Big O notation Complexity and recursion MAT 4 – Kompleks Funktionsteori What should we learn today? • What is computational complexity of algorithms? • When the growth of one function is higher (the same/ lower) than the growth of another function? • How we can estimate complexity of functions that are defined recursively? • What type of problems will be at the exam? MAT 4 – Kompleks Funktionsteori Fra gamle eksamenationopgaver MAT 4 – Kompleks Funktionsteori Computational complexity theory • Algorithm: a detailed ”step by step” description of a method • Complexity theory investigates the problems related to the amount of resources required for the execution of algorithms (e.g. execution time) • Complexity theory is also dealing with the scalability of computational problems and algorithms – As the size of the input to an algorithm increases, how do the running time and memory requirements of the algorithm change MAT 4 – Kompleks Funktionsteori Time complexity • The time complexity of a problem is the number of steps it takes to solve the problem. It is a function of the size of the input. • Example. It takes 1 min to mow a lawn of 10 m^2. 2 min – 20 m^2 … N min – N x 10 m^2 • The time complexity is linear MAT 4 – Kompleks Funktionsteori Addition • Example. Addition of 2 numbers with n digits • We perform n *simple* operations of type a+b+m (m is carry) • Assume that the time needed to perform a simple operation is s sec; the time needed to write down the last carry is t sec Total time required is sn+t • complexity is linear with respect to the number of digits MAT 4 – Kompleks Funktionsteori Multiplication • Example 1: multiplication of n-digit number with 1-digit number • The number of *simple* operations (ab+m) is n • Complexity is linear • Example 2: multiplication of two n-digit numbers consists of n multiplications of 1-digit and n-digit numbers ( n2 operations) + summation (n times addition of n-digit numbers n2 operations) • Complexity is quadratic MAT 4 – Kompleks Funktionsteori Big-O notation • This notation is used to describe how the size of the input data affects algorithm’s usage of resources (e.g. computational time) • Q: what is faster: to add or to multiply? • Definition. f(n) has the higher order growth then g(n), if the ratio f(n)/g(n) goes to infinity as n goes to infinity. • Note: both f(n) and g(n) are functions taking on positive values and they are increasing functions starting from a certain point. • Example: • Example: polynomials of degree m and k MAT 4 – Kompleks Funktionsteori Big-O notation • Definition. f and g has the same order growth, if their ratio f/g goes to a positive constant when n goes to infinity. • Example. Polynomials of the same degree MAT 4 – Kompleks Funktionsteori Big-O notation • Definition. Let f(n) be a positive, increasing function starting from a certain point. O(f) is a collection (set) of functions that exhibit a growth that is limited to the growth of f(n) (growth of smaller order or the same order as f(n) ) • Examples, propositions, properties… MAT 4 – Kompleks Funktionsteori Exponential, polynomial, logarithmic functions • Exponential growth an • Polynomial growth na • Logarithmic growth (logarithmic function is inverse to exponential function ) log n • Proposition. – Exponential function has a higher order growth than any polynomial function. – Polynomial function has a higher order growth than a logarithmic function. MAT 4 – Kompleks Funktionsteori MAT 4 – Kompleks Funktionsteori Complexity and recursion • Example: factorial function is defined recursively • t(n) is computational complexity: • Example: Fibonacci numbers • Computational complexity: MAT 4 – Kompleks Funktionsteori