tailieunhanh - Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 1 - Trịnh Anh Phúc

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" cung cấp cho người đọc các kiến thức: 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. . | Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 1 - Trịnh Anh Phúc 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; iThuật toán trực tiếp • Phân tích thuật toán: Ta sẽ tính số lượng phép cộng mà thuật toán phải thực hiện, tức là đếm xem dòng lệnh Sum += a[k] phải thực hiện bao nhiêu lần. Số lượng phép cộng sẽ là n 1 n 1 n 1 n 1 (n i)( n i 1) ( j i 1) (1 2 . (n i)) i 0 j i i 0 i 0 2 1 n 1 n 2 n 1 n(n .