tailieunhanh - Bài giảng Phân tích thiết kế giải thuật: Chương 2 - Trịnh Huy Hoàng

Bài giảng Phân tích thiết kế giải thuật: Chương 2 do Trịnh Huy Hoàng biên soạn sau đây sẽ bổ sung thêm cho các bạn những kiến thức về phân tích các thuật toán sắp xếp và tìm kiếm. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này. | Chương 2: Phân tích các thuật toán sắp xếp và tìm kiếm Trịnh Huy Hoàng Khoa Công nghệ thông tin Đại học Sư phạm TPHCM Mục đích Áp dụng kí pháp O lớn để phân tích đánh giá các phương pháp sắp xếp: Sắp xếp bằng phương pháp chọn (selection sort) Sắp xếp bằng phương pháp chèn (insertion sort) Sắp xếp bằng phương pháp đổi chỗ (interchange sort) Sắp xếp bằng phương pháp nổi bọt (bubble sort) Sắp xếp bằng phương pháp Shell (Shell Sort) Sắp xếp bằng phương pháp trộn (merge sort) Sắp xếp bằng phương pháp vun đống (heap sort) Sắp xếp nhanh (quick sort) Sắp xếp bằng phương pháp thẻ (bucket sort) Sắp xếp bằng phương pháp cơ số (radix sort) Sắp xếp bằng phương pháp chọn Ý tưởng: Tìm phần tử nhỏ nhất đưa về đầu dãy hiện tại Tiếp tục thực hiện phần còn lại của dãy Thuật toán: Algorithm selectSort(A) Input: Một mảng n phần tử số A Output: Mảng A đã được sắp xếp tăng dần. For i ← 1 to n-1 do min ← i For j ← i+1 to n do if A[j] Phân tích SX bằng pp chọn Vòng lặp ngoài (biến i) được thi hành n-1 lần: O(n) Tăng i: n-1 lần Kiểm tra i: n lần Gán i vào min: n-1 lần Đổi chỗ: tối đa n-1 lần Với mỗi giá trị của i, vòng lặp trong (biến j) được thi hành n-1-i lần tổng cộng (n-1) + (n-2) + + 1 = (n-1)n/2 lần: O(n2) So sánh: (n-1)n/2 lần Gán: tối đa (n-1)n/2 lần Phân tích SX bằng pp chọn (tt) Thời gian thực thi: T(n) = O(n) + O(n2) = O(n2+n) = O(n2) Sắp xếp bằng phương pháp chèn Ý tưởng: Chèn từng phần tử một vào dãy đã được sắp xếp đến bước hiện tại, vào đúng vị trí của nó để bảo đảm sau khi chèn dãy vẫn có thứ tự Thuật toán: Algorithm insertSort(A) Input: Một mảng n phần tử số A Output: Mảng A đã được sắp xếp tăng dần. For i ← 2 to n do temp ← A[i] j ← i - 1 while temp 0 do A[j+1] ← A[j] j ← j - 1 A[j+1] ← temp Return array A Phân tích thuật toán SX bằng pp chèn Vòng lặp for (biến i) được thực hiện n-1 lần Tăng i: n-1 lần So sánh i với n: n lần Gán giá trị vào các biến . | Chương 2: Phân tích các thuật toán sắp xếp và tìm kiếm Trịnh Huy Hoàng Khoa Công nghệ thông tin Đại học Sư phạm TPHCM Mục đích Áp dụng kí pháp O lớn để phân tích đánh giá các phương pháp sắp xếp: Sắp xếp bằng phương pháp chọn (selection sort) Sắp xếp bằng phương pháp chèn (insertion sort) Sắp xếp bằng phương pháp đổi chỗ (interchange sort) Sắp xếp bằng phương pháp nổi bọt (bubble sort) Sắp xếp bằng phương pháp Shell (Shell Sort) Sắp xếp bằng phương pháp trộn (merge sort) Sắp xếp bằng phương pháp vun đống (heap sort) Sắp xếp nhanh (quick sort) Sắp xếp bằng phương pháp thẻ (bucket sort) Sắp xếp bằng phương pháp cơ số (radix sort) Sắp xếp bằng phương pháp chọn Ý tưởng: Tìm phần tử nhỏ nhất đưa về đầu dãy hiện tại Tiếp tục thực hiện phần còn lại của dãy Thuật toán: Algorithm selectSort(A) Input: Một mảng n phần tử số A Output: Mảng A đã được sắp xếp tăng dần. For i ← 1 to n-1 do min ← i For j ← i+1 to n do if A[j] < A[min] then min ← j swap(A, i, min) Return array A .

• Kỹ thuật lập trình
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Thuật toán sắp xếp
• Phân tích thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phân tích thuật toán tìm kiếm
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Phân tích thuật toán
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Phân tích thiết kế thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Giải thuật xấp xỉ
• Bài toán che phủ đỉnh
• Bài toán NP đầy đủ
• Phân tích thiết kế giải thuật chương 37
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Cắt tỉa Alpha Beta
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Single Source Shortest Paths
• Phân tích thiết kế giải thuật chương 10
• Giải bài toán các đường đi ngắn nhất
• Biểu diễn các đường đi ngắn nhất
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Cây khung nhỏ nhất
• Giải thuật tổng quát
• Giải thuật của Kruskal
• Giải thuật của Prim
• Phân tích giải thuật
• Hệ thức truy hồi
• Độ phức tạp giải thuật
• Phân tích giải thuật lặp
• Phân tích giải thuật đệ quy
• Phân tích thuật giải
• Thiết kế thuật giải
• Chiến lược thiết kế thuật giải
• Quy hoạch động
• Biểu diễn thuật giải
• Phân tích thiết kế thuật toán
• Kỹ thuật tối ưu hóa chương trình
• Mức thiết kế một chương trình
• Kỹ thuật tinh chế mã
• Kỹ thuật tối ưu hóa rẽ nhánh
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Chia để trị
• Giải thuật quay lui
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• Giải thuật sắp xếp
• Chương trình sắp xếp
• Cấu trúc dữ liệu
• Giải thuật lưu trữ ngoài
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• Hình học tính toán
• Giải thuật thô sơ
• Kỹ thuật quét
• Tính đúng đắn
• Kỹ thuật mã hóa
• Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Đệ quy tuyến tính
• Đệ quy nhị phân