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!
Nội dung trích xuất từ tài liệu:
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 ƯỚ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 TP.HCM (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, …) 2Nộ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 3THỜI GIAN CHẠYCỦA THUẬT TOÁNTạ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 5Thời gian chạy của thuật toán• Phép toán cơ bảnPhép toán cơ bản (primitive operators) là phéptoá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 , +, −,×,/, >, Thời gian chạy của thuật toán• Thời gian chạy của thuật toánThời gian chạy của thuật toán (running time) làtổng số phép toán cơ bản (=, +, −, ×,/,>,…) 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 7Thờ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 thời gian chạy của thuật toán sau ① index = -1; ② for (int i=0; iPhân loại thời gian chạy của thuật toán• Thời gian chạy của thuật toán có thể phân làm 3 loại • Thời gian chạy trong trường hợp xấu nhất (worst case) • Thời gian chạy trong trường hợp tốt nhất (best case) • Thời gian chạy trong trường hợp trung bình (average case) 11Vấn đề với running time• Việc đếm chính xác số lượng phép toán nhiều lúc rất tốn công sức• Cách tính running time vẫn còn phụ thuộc • Ngôn ngữ lập trình: C, C#, Rust, Python, … • Kỹ thuật cài đặt 12 Vấn đề với running time • Ví dụ: tính thời gian chạy của thuật toán sau Input : ?? = (?? ?? , ?? ?? , … , ?? ?? ) ∈ ℝ ?? Algorithm: Sum of Array Output: Giá trị ?????? là tổng giá trị của ?? ?????? ← 0 for l ← 1 to ?? do ?????? ← ?????? + ??[??] end return ??????① sum=0; ① sum=0;② for (int i=0; iVấn đề với running time• Xây dựng thước đo mới • Một công cụ đo lường hay ước lượng (estimate) running time đơn giản hơn • Vẫn có chức năng như running time • Không phụ thuộc ngôn ngữ lập trình, kỹ thuật cài đặt • Cùng một thuật toán khi cài có thể là: ?? ?? = 2??, ?? ?? =• Nhận xét 6??, … hằng số 2, 6 là do kỹ thuật cài đặt • Nói chung: ??(??) ≤ ??. ?? (với ?? là một hằng số phù hợp) • ?? là do kỹ thuật cài đặt • ??(??) = ?? độc lập với kỹ thuật cài đặt 14KHÁI NIỆM BIG OKhái niệm Big O• Định nghĩa ???? ?? ????(??) = ??(??(??)) nếu tồn tại hằng số ??, ??0 > 0sao cho ?? ?? ≤ ??. ??(??) với mọi ?? ≥ ??0 • ?? ?? = 4?? + 3 ⟹ ?? ?? = ??(??)• Ví dụ • ?? ?? = 2??2 + 3?? + 4 ⟹ ?? ?? = ??(??2 ) 16Khái niệm Big O• Ý nghĩa của Big (O) • Nếu thuật toán có thời gian là ??(??(??)) nghĩa là thuật toán có số phép toán nhỏ hơn ??. ??(??) với c là một ...