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

Tham khảo tài liệu 'một số vấn đề về thuật toán part 3', 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ả | . Định lí cơ bản cho phân tích thuật toán 49 Ị Kan đúng với mọi n là đủ. Thật vậy ị -Xn 1 í bG I xn I 4- bp j xn_p I 4-G n bũKơ 1 bpKan p G n Kan-p bGap --- bp G n Kar -p ap -t G n Ka 1 - tKan p - G n Kct i 1. Đó lầ điều cần chứng minh. . ĐỊNH Lí Cơ BẢN CHO PHÂN TÍCH THUẬT TOÁN Phân tích thuật toán là đi tìm hàm thời gian thực hiện của thuật toán và thưòng rút ra phương trình truy hồi cho các hẩm hồi quy này. Một định lí cơ bản cho việc tìm hàm hồi quy loại này là Định lý . Nêỉi n ỉầ lũy thừa của c thì nghiệm của phương trình hồi quy . I d nêu n I Tin . néun i. có công thức sau O n nếu a c O nlogn nếu ữ c Ofn108 1 nê ua c. Chứng zw ọA. Nếu n là lũy thừa của c thì T n ữ T bn a T bn _ .2 Tp . abn a - bn ci c lí t n . bn . abn -a a T rs c bn 1 í n crbn . abn a T gr c bn 50 Chương ĩ. Công cụ đềphân tích t à thiết kế thuật toán Ta đặt i logrn cho ta công thức T - T bn E í . Ta có những công thức sau từ tính chất lôgarit ữ1og .n ú lo n _ log .njtolr _ nlog 1 Do đó l aỵj T n d-ri -a bn m . 0 c Ta xét ba trường hợp cho tổng vế phải của bất đẳng thức trên Trường hợp 1. a c Trường hợp này tổng ở vế phải được đánh giá chuôi của những số hạng là câ p số nhãn oo S 9 Ẻ 9 Do đó T n dn -a O ri VÌ thừa so thứ nhất có a c thỉ không ánh hướng đên sự đánh giá trên. Trườnghợp c Khi đó log n-1 T riị rf-n1 8 bn 1 Ofntogn . j 0 Trường hợp 3. a c Khi đó tổng của một cấp số nhân ở vế phải 7 d-n bn Ị Ỵ d-n a bn r ------------ j ũ Vc c 1 _ t d n bn 7 - Ota 08 -1 C 1 - Từ định lí trên ta suy ra những trường hợp sau đây Nếu T n 2T j dn thì T n ỡ n . Nếu T n 2T ị đn thì T ri O n log ri . Đây là công thức của thuât toán mergesort. Nếu T n 4T dn thì T n O n2 . . Bài tập 51 . BÀI TẬP _ s 1 . 1 t . Chứng minh răng i JJJ- với mọi n I. 1 2 2 t . Chứng minh rằng 2 2 1 1 - 1 với mọi n 0. j 0 . Cho số thực X G R . Kí hiệu x là số nguyên lớn nhất không lớn hơn .V. Còn Y là sô nguyên nhỏ nhâ t mà không nhỏ hơn X. Chứng minh rằng a Với mọi n 0 đẳng .