5无 PROBLEM 4口，￥①卡43，t夏，3)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, 4口，1①，43，t夏，里0Q0 Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms farch05.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. 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.cdu.cn2-2 The Efficiency of Algorithms farch05.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, 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.cdu.cn2-2 The Efficiency of Algorithms farch05.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. 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.cdu.cn2-2 The Efficiency of Algorithms farch05.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