tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Phân tích thuật toán - Nguyễn Mạnh Hiển

Bài giảng "Cấu trúc dữ liệu và giải thuật: Phân tích thuật toán" cung cấp cho người học các kiến thức: Phân tích độ phức tạp, phân tích độ phức tạp tiệm cận, ký hiệu Ô lớn, ký hiệu Ô-mê-ga lớn, ký hiệu Tê-ta lớn, tính chất bắc cầu, tốc độ tăng của một số hàm cơ bản. nội dung chi tiết. | Phân tích thuật toán Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@ Phân tích độ phức tạp Mục tiêu Đánh giá hiệu năng thời gian chạy và bộ nhớ chiếm dụng của các thuật toán Cho phép - So sánh các thuật toán khác nhau cùng giải một bài toán - Xem thời gian chạy biến thiên như thế nào theo kích thước dữ liệu đầu vào Phân tích độ phức tạp complexity bằng cách đếm số thao tác operation chiếm nhiều thời gian nhất Phân tích tiệm cận asymptotic analysis - Xem thời gian chạy tăng nhanh như thế nào khi kích thước đầu vào dần đến vô cùng Ví dụ đếm số thao tác Ví dụ 1 for i 0 i n i cout a i endl Số lần xuất n Ví dụ 2 Mã giả của phép nhân ma trận tam giác dưới và véc-tơ ci 0 i 1 to n for i 1 to n for j 1 to i ci aij j Số phép nhân si 1n i n n 1 2 Ví dụ 3 template class T bool isSorted T a int n bool sorted true for int i 0 i n-1 i if a i a i 1 sorted false return sorted Số phép so sánh n -