2-2 The Efficiency of Algorithms Hengfeng Wei hfwei@nju.edu.cn March 05,2020 Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms farch05,20201/43
2-2 The Efficiency of Algorithms Hengfeng Wei hfwei@nju.edu.cn March 05, 2020 Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 1 / 43
AN INTRODUCTION ANALYSIS ALGORITHMS S E CO N D E DI T I O N ROBE段T5 EDGEWICK PHILIPPE FLAJOLET The Analysis of Algorithms Hengfeng Wei (hfweixinju.edu.cn) 2-2 The Efficiency of Algorithms March05.20202/43
The Analysis of Algorithms Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 2 / 43
Donald E.Knuth (1938~) Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms March05.20203/43
Donald E. Knuth (1938 ∼) Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 3 / 43
A.M. TURING AWARD Donald E.Knuth (1974) "For his major contributions to the analysis of algorithms and the design of programming languages, and in particular for his contributions to the“art of computer programming”through his well-known books in a continuous series by this title." Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms March05,20204/43
Donald E. Knuth (1974) “For his major contributions to the analysis of algorithms and the design of programming languages, and in particular for his contributions to the “art of computer programming” through his well-known books in a continuous series by this title.” Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 4 / 43
Fibonacci numbers in the analysis of Euclid's GCD algorithm Hn in the analysis of FIND-MAX Stanford Lecture by Knuth "People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant math- ematical patterns that surround elegant computational pro- cedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically." Hengfeng Wei (hfweixinju.edu.cn) 2-2 The Efficiency of Algorithms March05,20205/43
Fibonacci numbers in the analysis of Euclid’s gcd algorithm Hn in the analysis of find-max @ Stanford Lecture by Knuth “People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.” Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 5 / 43
How Fast is It? Time (and Space)Complexity of Algorithms 02 o W Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms March05.20206/43
How Fast is It? Time (and Space) Complexity of Algorithms O Ω Θ o ω Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 6 / 43
Space Complexity of Algorithms We only care about the extra space caused by the algorithm. The space for inputs is not part of space complexity of algorithms. INSERTION-SORT(A,n):O(1)(constant) Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms March05,20207/43
Space Complexity of Algorithms We only care about the extra space caused by the algorithm. The space for inputs is not part of space complexity of algorithms. insertion-sort(A, n) : O(1) (constant) Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 7 / 43
Is it the Fastest? 2I63 Complexity of Problems This is much harder and is not our focus today. Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms March05,20208/43
Is it the Fastest? Complexity of Problems This is much harder and is not our focus today. Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 8 / 43
PROBLEM Whenever you design an algorithm, you provide an upper bound for the complexity of the problem. Whenever you encounter a "hardcore"of the problem, you obtain a lower bound for all possible algorithms. Often,there is an"algorithmic gap"between them. When the gap is gone,you get the optimal algorithm. sorting(A,n):θ(n log n)=O(n log n)∩2(n log n) Hengfeng Wei (bfweiinju.edu.cn)2-2 The Efficiency of Algorithms March05,20209/43
Whenever you design an algorithm, you provide an upper bound for the complexity of the problem. Whenever you encounter a “hardcore” of the problem, you obtain a lower bound for all possible algorithms. Often, there is an “algorithmic gap” between them. When the gap is gone, you get the optimal algorithm. sorting(A, n) : Θ(n log n) = O(n log n) ∩ Ω(n log n) Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 9 / 43
Q:How fast is your algorithm? A:It runs 3.1415926 seconds. TLE TIME LIMIT EXCEEDEEEED. TRICRS TO AVOID TLE IN COMPETITVE CODING B6OcKS Hengfeng Wei (hfweiinju.edu.cn2-2 The Efficiency of Algorithms March05,202010/43
Q : How fast is your algorithm? A : It runs 3.1415926 seconds. Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 10 / 43