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

Tham khảo tài liệu 'một số vấn đề về thuật toán part 4', 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ả | . Xác định độ phức tạp tính toán 73 phức tạpđược xác định như phần trước là max O p O í . Cũng như vậy ta nhận được độ phúc tạp của câu trúc nếu p không đúng là max ỡ p ơ s2 - Vì ta chựa biết đượckhối nào sẽ được thực hiện trong câu trúc này nên ta giả thiết rằng độ phức tạp của câu trúc là độ phức tạp lớn nhâ t của một trong hai khối này. Ta nhận được T ìí p then 51 else sì 6 max max ơ P ơ Fi max ớ P ơ F2 max O P O F1 O F2 . Tương tự ta cũng tính được độ phức tạp của câu trúc case. 5. Vông lặp for. Ta xét chu trình tính sau 1 fact ỉ 2 for i 1 to n do 3 fact . fact i 4 end for Ta có thể giả thiết phần bên trong của chu trình có hằng số thời gian tính c không phụ thuộc vào n. Dễ thây độ phức tạp của vòng lặp là ơ n . Bỏi vì theo nguyên tắc kết hợp ở trên thì độ phức tạp toàn bô chu trình là O cũng là ỡ n . Nếu tính chi tiết ra thì ta phải thêm vào độ phức tạp của khởi tạo biến trước khi có chu trình có độ phức tạp ơ l lại theo quy tắc dãy thứ tự phép toán thì có độ phức tạp Ơ L n . Nhưng cuối cùng theo các tính chất của hàm này thì độ phức tạp của chu trình trên là ỡ n . 6. Vòng lặp lổng nhàtL Ta xét hài vông lặp 1 sum Ó 2 for i 0 to n do 3 forj Otondo 4 sutn sum-ị- ỉ 5 end for 6 end for Độ phúc tạp tính toán của chu trình lồng nhau có chỉ số chạy độc lập có thể tính được dễ dàng vì đô phức tạp của một vòng lặp trong đã là O n và độ phức tạp của cả đoạn hai vàng lặp là T n n ơ n2 . Ta chú ý hơn chút nữa thì tổng cũng được tính với độ phức tạp o n2 74 Chương 3. Phăn tích độ phức tạp thuậi toán cho rằng mỗi phép tính cộng là hằng số ơ 1 . Do quy tắc dãy liên tiếp các phép tính nên độ phức tạp của đoạn chương trình hên chỉ là 0 n2 . Bây giờ ta xét vòng lặp có chỉ số phụ thuộc nhau 1 sum0 2 for i 0 to n 1 do 3 for j í to n do 4 sum 5wm l 5 end for 6 end for Dễ thâỳ phép tính sum sum 4-1 thực hiện 12 lần và như vậy độ phức tạp của đoạn chương trình trên cũng là ơ n2 . 7. Môt số ví dụ chu trình lổng nhau. Để làm quen với việc tính độ phức tạp tính toán của một