Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 1 Các khái niệm cơ bản với các nội dung chính như: Thuật toán và độ phức tạp, ký hiệu tiệm cận, giả ngôn ngữ, một số kĩ thuật phân tích thuật toán,. | CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN NỘI DUNG . Ví dụ mở đầu . Thuật toán và độ phức tạp . Ký hiệu tiệm cận . Giả ngôn ngữ . Một số kĩ thuật phân tích thuật toán Tham khảo tài liệu của PGS. TS. Nguyễn Đức Nghĩa Ví dụ mở đầu • Bài toán tìm dãy con lớn nhất: Cho dãy số a1, a2, , an Dãy số ai, ai+1 , , aj với 1 ≤ i ≤ j ≤ n được gọi là dãy con của dãy đã cho và ∑jk=i ak được gọi là trọng lượng của dãy con này Bài toán đặt ra là: Hãy tìm trọng lượng lớn nhất của các dãy con, tức là tìm cực đại giá trị ∑jk=i ak. Để đơn giản ta gọi dãy con có trọng lượng lớn nhất là dãy con lớn nhất. • Ví dụ: Nếu dãy đã cho là -2, 11, -4, 13, -5, 2 thì cần đưa ra câu trả lời là 20 (là trọng lượng của dãy con 11, -4, 13) Tham khảo tài liệu của PGS. TS. Nguyễn Đức Nghĩa Thuật toán trực tiếp • Thuật toán đơn giản đầu tiên có thể nghĩ để giải bài toán đặt ra là: Duyệt tất cả các dãy con có thể ai, ai+1 , , aj với 1 ≤ i ≤ j ≤ n và tính tổng của mỗi dãy con để tìm ra trọng lượng lớn nhất. • Trước hết nhận thấy rằng, tổng số các dãy con có thể của dãy đã cho là C(n,2) + n = n2/2 + n/2 . Tham khảo tài liệu của PGS. TS. Nguyễn Đức Nghĩa Thuật toán trực tiếp • Thuật toán này có thể cài đặt trong đoạn chương trình sau: int maxSum = 0; for (int i=0; i maxSum maxSum = sum; } } Tham khảo tài liệu của PGS. TS. Nguyễn Đức .
