Design and Analysis of Algorithms 2.Basics of algorithm design analysis Mingyu XIAO School of Computer Science and Engineering University of Electronic Science and Technology of China
Design and Analysis of Algorithms 2. Basics of algorithm design & analysis Mingyu XIAO School of Computer Science and Engineering University of Electronic Science and Technology of China
2.1 Analysis Consider the following problems: 1.What is the difference between polynomial time and exponential time? 2.How to evaluate the running time and space? 3.How to denote the running time or space?
2.1 Analysis Consider the following problems: 1. What is the difference between polynomial time and exponential time? 2. How to evaluate the running time and space? 3. How to denote the running time or space?
How To Measure the Running Time Use a clock to calculate the running time? --May not be good. We Hope:there is a uniform standard for all instances. For most algorithms,the running time and space are related to the size of the input. Different types of running times: Worst case running time.Obtain bound on largest possible running time of algorithm on input of a given size N. Average case running time.Obtain bound on running time of algorithm on random input as a function of input size N. 3
3 How To Measure the Running Time Different types of running times: Worst case running time. Obtain bound on largest possible running time of algorithm on input of a given size N. Average case running time. Obtain bound on running time of algorithm on random input as a function of input size N. Use a clock to calculate the running time? --May not be good. We Hope: there is a uniform standard for all instances. For most algorithms, the running time and space are related to the size of the input
How To Measure the Running Time There are also some other kinds of running times, such as smooth analysis and son. We only consider worst case running time in this course. Questions: Why do we consider worst case running time for most problems? If the worst case running time is W,then there is at least one instance that the running time of it is W?
4 How To Measure the Running Time There are also some other kinds of running times, such as smooth analysis and son. We only consider worst case running time in this course. Questions: Why do we consider worst case running time for most problems? If the worst case running time is W, then there is at least one instance that the running time of it is W?
How To Measure the Running Time Consider this problem:Max independent set problem To find a vertex set of max cardinality in a given graph such that no pair of vertices in the set are adjacent. A Brute force method for this problem:For many non-trivial problems,there is a natural brute force search algorithm that checks every possible solution. What is the worst case running time of this algorithm? It takes 2N time for inputs of size N(N vertices). (any problem for this algorithm?)
5 How To Measure the Running Time Consider this problem: Max independent set problem To find a vertex set of max cardinality in a given graph such that no pair of vertices in the set are adjacent. A Brute force method for this problem: For many non-trivial problems, there is a natural brute force search algorithm that checks every possible solution. What is the worst case running time of this algorithm? It takes 2N time for inputs of size N (N vertices). (any problem for this algorithm?)