2-2 The Efficiency of Algorithms Hengfeng Wei hfwei@nju.edu.cn March 05,2020 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms March05,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 4口·￥①，43，t夏，里Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-2 The Efficiency of Algorithms farch05.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~) 4口，1①，43，t夏，里0Q0 Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms farch05.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) 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms farch05.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
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." 4口·￥①，43，t夏，2)Q0 Hengfeng Wei (bfweiinju.edu.cn)2-2 The Efficiency of Algorithms March 05.2020 4/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
"People who analyze algorithms have double happiness. 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms farch05.20205/43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . “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
"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. 4口￥0,43，t夏，里Q0 Hengfeng Wei (hfweiinju.cdu.cn2-2 The Efficiency of Algorithms March05,20205/43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . “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
Fibonacci numbers in the analysis of Euclid's GCD algorithm "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. 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.cdu.cn2-2 The Efficiency of Algorithms farch05.20205/43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fibonacci numbers in the analysis of Euclid’s gcd algorithm “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
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. 4口￥0,43，t夏，里Q0 Hengfeng Wei (hfweiinju.cdu.cn2-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
"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." 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.cdu.cn2-2 The Efficiency of Algorithms March05,20205/43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . “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