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. 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.cdu.cn2-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
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. 4口，￥①，43，t更，里Q0 Hengfeng Wei (hfweinju.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
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? 4口·￥①，43，t夏3)Q0 Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms Aarch05,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
Q:How fast is your algorithm? A:It runs 3.1415926 seconds. TLE TIME LIMIT EXCEEDEEEED. TRICRS TO AVOID TLE IN COMPETITVE CODING B8Kg 4口￥0,43，t夏，里Q0 Hengfeng Wei (hfweiinju.edu.cn)2-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