tailieunhanh - Bài giảng Phân tích và thiết kế thuật toán: Hoán vị và ứng dụng - Phạm Thế Bảo

Bài giảng Phân tích và thiết kế thuật toán này giới thiệu về thuật toán hoán vị và ứng dụng của thuật toán hoán vị. Trong bài giảng này người học sẽ tìm hiểu một vài khái niệm cơ bản, nghịch thế trong hoán vị, các phần tử cực đại bên phải. để nắm bắt các nội dung chi tiết. | HOÁN VỊ VÀ ÚNG dụng Phạm Thề Bào Khoa Toan - Tin học Trường Đại học Khoa học Tự nhiên Vài khái niệm cơ bản s tập họp có n phần tư. Một hoán vị cua s là một song ánh ô S- S Ví dụ s 1 2. 3 8 s - s 1 - 3 2 1 Nếu s 1 2 3 . 11 và dòng trên luôn được hiểu sap là 1 2 3 . n thi ta chỉ viết dòng dưới. Ví dụ 8 3 12 Phạm Th ế Bảo Printed with FinePrint - purchase at Nếu S n thi có bao nhiêu hóan vị cách sắp xếp chúng cua s Hàm gia thừa này tăng rât nhanh 10 3628800 Một cách tính gia thùa khác đó là công thức Stirling n a 2 th với e khi n đủ Iđn Vậy 0 n O nn và O log n O nlog n Ph ạm Th ế Bảo Printed with FinePrint - purchase at Nghịch thê a. Định nghĩa cho ab a2 . an là một hoán vị cua n . Neu i j và a a thi cặp ap 3j là một nghịch thế cua hóan vị đang xét. Vídụ ô 3 1 4 2 có các nghịch thế là 3. 2 4. 2 Vậy một hoán vị có n phần tu thì có bao nhiêu nghịch thế vì một số thuật toán có thời gian thục hiện phụ thuộc vào số nghịch thế . Phạm Th ế Bảo Vi dụ cho n phần tu phân biệt a l a 2 . a n . Thuật toán tạo chỉ mục sao cho a i b Index i với b là một hoán vị cua n và ta có b l b 2 . b n . Index i số phần tu cua a nho hon a i 1 Phạm Th ế Bảo Printed with FinePrint - purchase at .