Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Đỗ Ngọc Như Loan

Chia sẻ: Dien_vi10 Dien_vi10 | Ngày: | Loại File: PPTX | Số trang:31

Thêm vào BST

Báo xấu

43
lượt xem 2
download

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

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về cấu trúc dữ liệu & giải thuật" cung cấp cho người học các kiến thức: Độ phức tạp của thuật toán, biểu diễn thời gian chạy bởi ký hiệu O. 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 Cấu trúc dữ liệu và giải thuật: Chương 1 - Đỗ Ngọc Như Loan

GV: Đỗ Ngọc Như Loan
Cấu trúc dữ liệu là gì?
Cấu trúc dữ liệu là cách tổ chức lưu trữ dữ liệu sao cho hiệu quả nhất Thế nào là hiệu quả? 1. Chính xác 2. Dùng ít bộ nhớ 3. Khả năng tìm kiếm/truy xuất 4. Khả năng cập nhật, thêm (modification, insertion / deletion) 5. Đơn giản, dễ hiểu
Giải thuật là gì?
Thuật toán là một phương pháp bao gồm một dãy các bước tính toán để giải quyết một bài toán. Thuật toán có thể được diễn tả dưới ngôn ngữ tự nhiên (tiếng Việt, tiếng Anh…), mã giả hay ngôn ngữ lập trình (C++, Java…) Thế nào là một thuật toán tốt? 1. Đúng đắn 2. Nhanh 3. Ít bộ nhớ 4. Đơn giản, dễ hiểu
Ví dụ Tìm x trong dãy a1, a2, ...., an Input: Số x, dãy n số a1, a2, ..., an Output: Một giá trị logic true hoặc false Search(x, a, n) for i  1 to n do if ai = x then return true return false
Một vấn đề có thể được giải quyết bẳng nhiều thuật toán khác nhau
Ví dụ Tính tổng các số nguyên từ 1 đến n. Input: n (n >1) Output: Tổng các số nguyên từ 1 đến n
Cách 1 sum = 0; for (int i = 1; i
Độ phức tạp Cách 1 O(n) sum = 0; for (int i = 1; i
ĐỘ PHỨC TẠP THUẬT TOÁN Độ phức tạp của giải thuật là chi phí về tài nguyên của hệ thống (chủ yếu là thời gian, bộ nhớ, CPU, đường truyền) cần thiết để thực hiện giải thuật  Độ phức tạp về không gian (dung lượng bộ nhớ sử dụng)  Độ phức tạp về thời gian Phân tích giải thuật (Analyzing of Algorithm) là quá trình tìm ra những đánh giá về tài nguyên cần thiết để thực hiện giải thuật
ĐỘ PHỨC TẠP THUẬT TOÁN Độ phức tạp về thời gian của giải thuật: • Được qui về đếm số lệnh cần thực thi của giải thuật • Đó là một hàm T(n) phụ thuộc vào kích thước n của input • Coi như có một máy trừu tượng (abstract machine) để thực hiện giải thuật
ĐỘ PHỨC TẠP THUẬT TOÁN • Thời gian tối thiểu để thực hiện giải thuật với kích thước đầu vào n gọi là thời gian chạy tốt nhất (bestcase) của giải thuật • Thời gian nhiều nhất để thực hiện giải thuật với kích thước đầu vào n được gọi là thời gian chạy xấu nhất (worstcase) của giải thuật • Thời gian trung bình để thực hiện giải thuật với kích thước đầu vào n được gọi là thời gian chạy trung bình (average case) của giải thuật
Ví dụ Đánh giá độ phức tạp về thời gian của giải thuật Search(x, a, n) for i  1 to n do if ai = x then return true return false
 dssdsdsssssssssssslkcddkcf;dxkac
BIỂU DIỄN THỜI GIAN CHẠY BỞI KÝ HIỆU O Giả sử f(n) và g(n) là hàm thực không âm của đối số nguyên dương n, ta nói f(n) = O(g(n)) nếu có hằng số c > 0 và số nguyên dương N sao cho f(n) = N Nếu giải thuật có thời gian chạy tốt nhất (trung bình, xấu nhất) là T(n) và T(n) = O(g(n)) thì ta nói độ phức tạp của giải thuật trong trường hợp tốt nhất (trung bình, xấu nhất) là O(g(n))
Ví dụ: Giả sử f(n) = 5n3 + 2n2 + 13n + 6 , ta có: f(n) = 5n3 + 2n2 + 13n + 6 =1) f(n) = O(n3) Tổng quát nếu f(n) là một đa thức bậc k của n: f(n) = aknk + ak1nk1 + ... + a1n + a0 thì f(n) = O(nk)
Quy Tắc  QUY TẮC CỘNG: Nếu đoạn chương trình P1 có thời gian thực hiện T1(n) = O(f(n)) và đoạn chương trình P2 có thời gian thực hiện là T2(n) = O(g(n)) thì thời gian thực hiện P1 rồi đến P2 tiếp theo sẽ là: T1(n) + T2(n) = O(f(n) + g(n))  QUY TẮC NHÂN: Nếu đoạn chương trình P có thời gian thực hiện là T(n) = O(f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) = O(g(n)) thì độ phức tạp tính toán sẽ là O(g(n). f(n))  QUY TẮC MAX: Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(f(n) + g(n)) thì có thể coi đoạn chương trình đó có độ phức tạp
Độ phức tạp (tăng dần) • O(1) Hằng số • O(log2n) Logarithm • O(n) Tuyến tính • O(nlog2n) n log n • O(n2) Bậc hai • O(n3) Bậc ba • O(nm) Đa thức • O(mn), m >= 2 Hàm mũ • O(n!) Giai thừa
VÍ DỤ  Viết và phân tích giải thuật tính giai thừa của số tự nhiên n.