tailieunhanh - Bài giảng Toán rời rạc: Độ phức tạp của thuật toán - ThS. Hoàng Thị Thanh Hà

Bài giảng Toán rời rạc - Độ phức tạp của thuật toán, được biên soạn gồm các nội dung chính sau: Giới thiệu; Định nghĩa; Đánh giá thuật toán. Mời các bạn cùng tham khảo! | Toán rời rạc 1b ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Ths. Hoàng Th Thanh Hà Khoa Th ng kê Tin h c Trư ng Đ i h c Kinh t Đ i h c Đà N ng 22 August 2012 1 Nội dung 1. Giới thiệu 2. Định nghĩa 3. Đánh giá thuật toán 22 August 2012 2 1 Giới thiệu Các thuật toán được đánh giá qua 2 chỉ tiêu Thời gian là số thao tác mà thuật toán thực hiện tương ứng với kích thước nhập n Không gian là kích thước bộ nhớ mà thuật toán sử dụng Ví dụ 1 Xét thuật toán tìm số lớn nhất trong dãy n số a1 a2 . an. Nếu coi mỗi lần so sánh hai số của thuật toán đòi hỏi một đơn vị thời gian giây chẳng hạn thì thời gian thực hiện thuật toán trong trường hợp xấu nhất là n-1 giây. Với dãy 64 số thời gian thực hiện thuật toán nhiều lắm là 63 giây. 22 August 2012 3 Giới thiệu Ví dụ 2 Thuật toán về trò chơi Tháp Hà Nội có ba cọc A B C và 64 cái đĩa các đĩa có đường kính đôi một khác nhau. Nguyên tắc đặt đĩa vào cọc là mỗi đĩa chỉ được chồng lên đĩa lớn hơn nó. Ban đầu cả 64 đĩa được đặt chồng lên nhau ở cột A hai cột B C trống. Vấn đề là phải chuyển cả 64 đĩa đó sang cột C lấy cột B làm trung gian mỗi lần chỉ được di chuyển một đĩa. Gọi Sn là số lần chuyển đĩa để chơi xong trò chơi với n đĩa Nếu n 1 thì rõ ràng là S1 1 Nếu n gt 1 thì trước hết chuyển n-1 đĩa bên trên sang cọc B. Số lần chuyển n-1 đĩa là Sn-1. Sau đó ta chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng ta chuyển n-1 đĩa từ cọc B sang cọc C số lần chuyển là Sn-1 . gt số lần chuyển n đĩa từ A sang C là Sn Sn-1 1 Sn 1 2Sn- 1 1 2 2Sn 2 1 1 2 1 . 2n-1S1 2n-2 . 2 1 2 1. n 22 August 2012 4 2 Giới thiệu Thuật toán về trò chơi Tháp Hà Nội đòi hỏi 264 1 lần chuyển đĩa xấp xỉ 18 4 tỉ tỉ lần . Nếu mỗi lần chuyển đĩa mất 1 giây thì thời gian thực hiện thuật toán xấp xỉ 585 tỉ năm Thuật toán trong ví dụ 1 có độ phức tạp là n-1 và là một thuật toán hữu hiệu hay thuật toán nhanh Thuật toán trong ví dụ 2 có độ phức tạp là 2n 1 và đó là một thuật toán không hữu hiệu hay thuật toán chậm 22 August 2012 5 Định nghĩa Định nghĩa 1 Ta nói hàm f n có độ phức tạp .

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Độ phức tạp của thuật toán
• Hàm bậc hai
• Hàm đơn thức
• Quy tắc nhân
• Thuật toán tìm kiếm tuyến tính
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc