intTypePromotion=1

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

0
22
lượt xem
0
download

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

Mô tả tài liệu
  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ủ đề:
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

  1. GV: Đỗ Ngọc Như Loan
  2. Cấu trúc dữ liệu là gì?
  3. 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
  4. Giải thuật là gì?
  5. 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
  6. 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
  7. Một vấn đề có thể được giải quyết  bẳng nhiều thuật toán khác nhau
  8. 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
  9. Cách 1 sum = 0; for (int i = 1; i 
  10. Độ phức tạp  Cách 1 O(n) sum = 0; for (int i = 1; i 
  11. ĐỘ 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
  12. ĐỘ 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
  13. ĐỘ 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 (best­case) 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 (worst­case) 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
  14. 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
  15.   dssdsdsssssssssssslkcddkcf;dxkac
  16. 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))
  17. 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 + ak­1nk­1 + ... + a1n + a0 thì f(n) =  O(nk)
  18. 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 
  19. Độ 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
  20. 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.
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2