tailieunhanh - Một số vấn đề về thuật toán part 5

Tham khảo tài liệu 'một số vấn đề về thuật toán part 5', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | . Thuật toán sắp xếp trộn 97 7 5 7 3 7 2 5 8 4 5 17 7 8 7 4 7 4 8 12 12 8 32 7 16 7 8 7 8 16 32 32 16 80. 7 32 7 16 7 16 32 80 80 32 192 Với n bất kỳ thì chưa tìm ra một quy luật nào. Ta có thể thây với n là lũy thừa của 2 thì khi đó ta có 7 8 1 r 2 2 . 8 r 6 16 7 32 32 5 6. r 4 _ 3 ỉ í Thế thì ta có thể dự đoán là Ign 1 hay tương đương với 7 n nlgn n nghĩa là 7 n 0 nlgn . Nhưng đó không phải là chửng minh. Có rất nhiều cách chứng minh đãng thức sau cùng này như chương trước đã nói tới. Ta sẽ chứng minh bằng phương pháp quy thể bỏ đi Cí Trong những biểu thức có những hàm như thế này ta Cố thể bỏ đi các hàm nàý chỉ còn đại lượng n bằng cách giả thiết rằng n là bội của 2. Ta chú ý là như vậy việc phân tích của ta chỉ đúng chó một tặp hợp hạn chế của giá trị n nhưng những giá trị khác lại nằm trong một lũy thừa 2 nào đó khi đó hàm đánh giá là một bết đẳng thức nên nó đúng với mọi n. Như vậy yới n là lũy thừa của 2 thi biểu thức truy hổi có dạng 7 n 1 nếun- lj 27 n nếun l. Mệnh để . Với mọi n lz n là bội của 1 công thức sau đây đúng T ii nỉgn n Ở đây Ig là lồgarììcơSỐ1. 98 Chương 4. Phương pháp chia để trị Chứng minh. Chứng minh bằng phương pháp quy nạp dạng 1 theo n. Bước cơ sỏ Với n ỉ ta có T l 1 theo định nghĩa và cổng thức 1 Ig 1 1 1 T 1 mệnh đề đúng. Bước quỵ nạp Cho n 1 và giả sử công thức T jt đúng với mọi k n. Ta phải chứng minh công thức đúng cho chính n. Muốn vậy ta phải biếu diễn T n thành thừa số với những giá trị nhỏ hơn. Đê làm điều đó ta áp dụng định nghĩa T 2rộ n. Do n ta có thế áp dụng giá thiết quy nạp vợi T -ị Â if ủt 1 Tổng hợp lại ta cỏ tỉ n n f n . T n 2U g2 ị n g2 n lgn lg2 2n nlgn-rt 2n nlgft n đó là điều ta cần chửng minh. . THUẬT TOÁN NHÂN HAI MA TRẬN Nhân hai ma trận cùng cỡ là một ví dụ điển hình cho việc thiết kế thuật toán chia để trị. Ta có hai ma trận y và z cỡ n X n. Theo định nghĩa phép nhân hai ma hận ta có công thức n xij V. yikZkj k ĩ ở đây yiJt và Zkj là những phần tử của các ma hận tương ứng Y z còn XiJ là phần tử trong .