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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:42

Thêm vào BST

Báo xấu

15
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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, …) 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 , +, −,×,/, >,
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 (=, +, −, ×,/,>,…) 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; i
Thờ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; i
Thờ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; i
Phâ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) 11
Vấ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; i
Vấ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 14
KHÁI NIỆM BIG O
Khái niệm Big O • Định nghĩa 𝐵𝐵𝐵𝐵 𝐵𝐵 𝑂𝑂 𝑇𝑇(𝑛𝑛) = 𝑂𝑂(𝑓𝑓(𝑛𝑛)) nếu tồn tại hằng số 𝑐𝑐, 𝑛𝑛0 > 0 sao cho 𝑇𝑇 𝑛𝑛 ≤ 𝑐𝑐. 𝑓𝑓(𝑛𝑛) với mọi 𝑛𝑛 ≥ 𝑛𝑛0 • 𝑇𝑇 𝑛𝑛 = 4𝑛𝑛 + 3 ⟹ 𝑇𝑇 𝑛𝑛 = 𝑂𝑂(𝑛𝑛) • Ví dụ • 𝑇𝑇 𝑛𝑛 = 2𝑛𝑛2 + 3𝑛𝑛 + 4 ⟹ 𝑇𝑇 𝑛𝑛 = 𝑂𝑂(𝑛𝑛2 ) 16
Khá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 hằng số • Ví dụ • 𝑂𝑂(𝑛𝑛2 ) thuật toán có thời gian chạy tối đa 𝑐𝑐. 𝑛𝑛2 • 𝑂𝑂(𝑛𝑛3 ) thuật toán có thời gian chạy tối đa 𝑐𝑐. 𝑛𝑛3 • So sánh: thuật toán 𝑂𝑂(𝑛𝑛2 ) có thời gian chạy nhanh hơn thuật toán 𝑂𝑂(𝑛𝑛3 ), … • 𝑂𝑂(. ) chỉ là ước lượng (estimate) thời gian chạy của chương trình 17
QUY TẮC TÍNH BIG O
Quy tắc tính Big O 𝑂𝑂 𝑐𝑐. 𝑓𝑓 𝑛𝑛 = 𝑂𝑂(𝑓𝑓(𝑛𝑛)) • Quy tắc hằng số • Đoạn chương trình thứ nhất: 𝑂𝑂 𝑓𝑓 𝑛𝑛 • Quy tắc cộng • Đoạn chương trình thứ hai: 𝑂𝑂 𝑔𝑔 𝑛𝑛 • Cả 2 đoạn chương trình: 𝑂𝑂 𝑓𝑓 𝑛𝑛 + 𝑔𝑔 𝑛𝑛 𝑂𝑂 𝑔𝑔 𝑛𝑛 + 𝑔𝑔 𝑛𝑛 = 𝑂𝑂 max(𝑓𝑓 𝑛𝑛 , 𝑔𝑔 𝑛𝑛) • Quy tắc max 19
Quy tắc tính Big O • Quy tắc nhân • Đoạn chương trình có độ phức tạp: 𝑂𝑂 𝑓𝑓 𝑛𝑛 • Thực hiện đoạn chương trình trên nhiều lần: 𝑂𝑂 𝑔𝑔 𝑛𝑛 • Độ phức tạp của các chương trình: 𝑂𝑂 𝑔𝑔(𝑛𝑛) × 𝑓𝑓 𝑛𝑛 20