Chặt nhị phân độ phức tạp là bao nhiêu năm 2024
|
Tài li ệ u b ồi dưỡ ng HSG môn Tin h ọ c Chuyên đề : K ỹ thu ậ t Ch ặ t nh ị phân – Nguy ễ n Chánh Tín – trườ ng THPT Chuyên B ạ c Liêu 1 S Ở GD&ĐT BẠ C LIÊU TRƯỜ NG THPT CHUYÊN B Ạ C LIÊU Chuyên đề bồi dưỡng HSG môn Tin học: Ứ Ứ NNGG DD ỤỤ NNGG K K ỸỸ TTHHUU ẬẬ TT CCHH ẶẶ TT NNHH ỊỊ PPHHÂÂNN TTR R OONNGG VVII ỆỆ CC GGII ẢẢ II CCÁÁCC BBÀÀII TTOOÁÁNN TTIINN HH ỌỌ CC GV Biên soạn : NGUYỄN CHÁNH TÍN Đơn vị : Trườ ng THPT Chuyên B ạ c Liêu Tháng 02/2018 Tài li ệ u b ồi dưỡ ng HSG môn Tin h ọ c Chuyên đề : K ỹ thu ậ t Ch ặ t nh ị phân – Nguy ễ n Chánh Tín – trườ ng THPT Chuyên B ạ c Liêu 2 M Ụ C L Ụ C Mục Nội dung Trang Lời mở đầu 3 1 Phần nội dung 4 2 I- Cơ sở lý thuyết 4 3 II- Chặt nhị phân theo kết quả 8 4 III- Ch ặ t nh ị phân trên dãy s ố . 19 5 K ế t lu ậ n 37 6 Tài li ệ u tham kh ả o 38 Tài li ệ u b ồi dưỡ ng HSG môn Tin h ọ c Chuyên đề : K ỹ thu ậ t Ch ặ t nh ị phân – Nguy ễ n Chánh Tín – trườ ng THPT Chuyên B ạ c Liêu 3 LỜI MỞ ĐẦU Hiện nay trong các kỳ thi, đề thi luôn yêu cầu vận dụng và phối hợp nhiều thuật toán một cách linh hoạt để giải bài toán. V ới mỗi bài toán học sinh không chỉ phải đưa ra được thuật toán đúng mà thuật toán đó còn phải tốt đáp ứng yêu cầu về thời gian để có thể “ăn” hết các test lớn . P hần lớn khi giải bài toán, chúng ta chỉ tập trung ở mức độ tìm thuật toán đúng cho bài toán. Chẳng hạn với bài toán sau: Cho một dãy số nguyên gồm N phần tử, hãy sắp xếp để dãy số đã cho trở thành dãy không giảm? Trước tiên chúng ta ai cũng nghĩ ngay đến thuật toán sắp xếp tráo đổi (thuật toán sắp xếp “nổi bọt”) có độ phức tạp O(N 2 ) . Đây là thuật toán đúng nhưng chỉ trong trường hợp N≤ 1 0 3 . N ếu tăng số lượng phần tử lên khoảng 10 5 phần tử thì ta cần một thuật toán sắp xếp tốt hơn như: QuickSort, MergeSort có độ phức tạp O(NlogN) . Từ vấn đề thực tiễn trên thì kỹ thuật “Chặt nhị phân” là một kỹ thuật sẽ giúp làm giảm thời gian thực hiện thuật toán từ O(K) xuống còn O(logK) . |
