tailieunhanh - Bài giảng Kỹ thuật lập trình: Chương 2 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

Bài giảng Kỹ thuật lập trình: Chương 2 Ước lượng độ phức tạp thời gian (Big O) của thuật toán, cung cấp cho người đọc những kiến thức như: Thời gian chạy của thuật toán; Khái niệm Big O; Quy tắc tính Big O; Một số Big O thông dụng; .Mời các bạn cùng tham khảo! | ƯỚC LƯỢNG ĐỘ PHỨC TẠP THỜI GIAN BIG O CỦA THUẬT TOÁN Khoa Công nghệ thông tin Trường Đại học Ngoại ngữ - Tin học HUFLIT Review 4 thành phần của bài toán Mô tả ngữ cảnh Mô tả input Mô tả output Các ví dụ Quy trình giải bài toán Đọc bài toán vài lần gạch dưới những từ quan trọng Giải bài toán trên giấy giải các ví dụ Tinh chỉnh lời giải Viết mã giả dự kiến các hàm các lớp Cài đặt chương trình cài đặt từng bước của mã giả Kiểm tra kiểm thử với những dữ liệu khác nhau chạy từng bước để phát hiện lỗi Các biểu diễn dữ liệu cơ bản Vô hướng Danh sách Bảng Dạng khác Tree Graph 2 Nội dung Thời gian chạy của thuật toán Khái niệm Big O Quy tắc tính Big O Một số Big O thông dụng 3 THỜI GIAN CHẠY CỦA THUẬT TOÁN Tại sao cần biết thời gian chạy của thuật toán Trong thiết kế thuật toán Định hướng thiết kế từ input size time limited định hướng cần phải thiết kế thuật toán có phức tạp bao nhiêu dùng phương pháp gì Đánh giá thuật toán có thể chạy trong thời gian cho phép không trước khi tiến hành cài đặt Xác định những điểm yếu trong thuật toán để cải tiến Trong sử dụng thuật toán Trước khi sử dụng một thuật toán trong thư viện cần biết thuật toán có thời gian chạy bao nhiêu Trong so sánh các thuật toán Là thước đo các thuật toán cùng giải quyết một bài toán 5 Thời gian chạy của thuật toán Phép toán cơ bản Phép toán cơ bản primitive operators là phép toán có thời gian chạy là một hằng số không phụ thuộc vào kích thước dữ liệu gt Thời gian chạy của thuật toán Thời gian chạy của thuật toán Thời gian chạy của thuật toán running time là tổng số phép toán cơ bản gt mà thước input size thuật toán thực hiện khi giải quyết bài toán trên dữ liệu vào có kích Ký hiệu Input size Input size Số lượng phần tử số phần tử dãy số số phần tử ma trận Giá trị của biến 7 Thời gian chạy của thuật toán Ví dụ tính thời gian chạy của thuật toán sau sum 0 for int i 0 iThời gian chạy của thuật toán Bài 1. tính thời giai chạy của thuật toán sau sum 0 for int i 0 iThời gian chạy của thuật toán Bài 3. tính