tailieunhanh - Bài giảng Cấu trúc dữ liệu - ThS. Nguyễn Thị thúy Loan

Bài giảng Cấu trúc dữ liệu trình bày các nội dung: Độ phức tạp thuật toán, tìm kiếm và sắp xếp, danh sách liên kết, Stack & Queue, cây và các nội dung cụ thể khác. Mời bạn đọc tham khảo tài liệu để hiểu thêm về các nội dung trên. | BÀI GIẢNG CẤU TRÚC Dữ LIỆU ThS. Nguyên Thị Thúy Loan 1. 2. 3. 4. 5. 6. Tài liệu tham khảo Bài giảng ThS. Nguyễn Hà Giang Cấu trúc dữ liệu giải thuật Dương Anh Đức Trần Hạnh Nhi NXB DHQG 2008. Cấu trúc dữ liệu Nguyễn Trung Trực ĐHBK 1992. Giải thuật lập trình Lê Minh Hoàng ĐHSPHN 1999-2002. Cấu trúc dữ liệu giải thuật chương trình Nguyễn Quốc Cường - Hoàng Đức Hải NXB Giáo dục. Fundamentals of Data Structures Ellis Horowitz Sartaj Sahni. 6 8 2010 Nguyên Thị Thúy Loan Cách đánh giá Thực hành 30 Bài tập 20 Lý thuyết 50 NỘI DUNG CHƯƠNG TRÌNH Độ phức tạp thuật toán. ịĨỊ rri kỉ í ệ rì yặ ẹặp xếp. Danh sách liên kết Stack Queue. Cây. 6 8 2010 Chương I Độ PHỨC TẠP THUẬT TOAN ThS. Nguyên Thị Thúy Loan NỘI DUNG I. ĐO THỜI GIAN II. DỰA VÀO Độ LỚN CỦA Dữ LIỆU III. MỌT SỐ CÔNG THỨC THƯỜNG DÙNG IV. CÁCH TÍNH ĐỌ PHỨC TẠP 6 8 2010 Nguyên Thị Thúy Loan Dựa vào độ lớn của dữ liệu ịịịpọi t rí ỉặ g ịạ ị ọỊị jrpp O h j. d0 phLFC ian thực hiện của thuật toán mg là chu kỳ của CPU t n g các loại tạp là một hằng số. Phép gán. í i 1 i - 10 i intf d i 1 .10 và i 11 để dừng 11. 1 i 1 .10 11. 6 8 2010 Nguyễn Thị Thúy Loan 8 Dựa vào độ lớn của dữ liệu b. O loq n Tìm nhị phân. c. O n Kiểm tra một số có phải là số nguyên tố VD Kiểm tra số nguyên tố xét i 2 n 2 nếu i là ước số của n n không phải là số nguyên tố ngược lại n là nguyên tố. 6 8 201Ũ Nguyễn Thị Thúy Dựa vảo độ lớn của dữ liệu e. f. g- áp dụng O n Độ phức tạp tuyến tính duyệt mảng dãy . O nloq2n thuật toán Logarit sắp xếp mảng . O na g 1 đa thức. O 2n O n mũ áp dụng liệt kê tất các tập con của tập gồm n phần tử . áp dụng cả d 6 8 2010 Nguyên Thị Thúy Loan 11 Dựa vào độ lớn của dữ liệu Nhân xét Trừ số 2 tất cả các số chẵn không phải là số nguyên tố. Các số lẻ không có ước số chẵn. i là ước số của n n i là ước số của n. Nguyên Thị Thúy Loan I Một sổ công thức thường dùng 7 2 77 77 I - ứ - l ứ - I I 2 7 2 7 2 1 l 2 .-ê . I -.