tailieunhanh - Giáo trình thuật toán và kỹ thuật lập trình Pascal part 8
Tham khảo tài liệu 'giáo trình thuật toán và kỹ thuật lập trình pascal part 8', 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ả | Các lệnh 1 2 và 3 được thực hiện một lần. Các lệnh 5 6 và 7 tạo ra thân của vòng lặp được thực hiện mỗi lệnh n lần và ệnh 4 kiểm tra sự lặp lại được thực hiện n 1 lần bởi phải thêm một lẩn kiểm tra bổ sung để xem biến i đã vượt qua giá trị n hay chưa. Sau khi kết thúc vòng lặp lệnh 8 được thực hiện một lần. Lệnh Số lần thực hiện 1 1 2 1 3 1 4 n 1 5 n 6 n 7 n 8 1 Tổng cộng 4n 5 Thời gian thực hiện thuật toán này là T n 4n 5 Ta có 4n 5 4n n 5n với mọi n 5. Vậy theo định nghĩa big-O chọn c 5 k 1 g n n ta có T n 0 n . Ta nói rằng thuật toán tính giá trị trung bình của n số cớ độ phức tạp bậc n. Nhận xét Thời gian tính toán như ở ví dụ chỉ phụ thuộc vào kích thước dữ liệu đầu vào. Trong nhiều vâh đề khác thời gian tính toán còn phụ thuộc vào thứ tự các mục của dữ liệu đầu vào. Ví dụ thời gian sắp xếp một dãy các sô nguyên đã được sắp xếp gần hết sẽ nhanh hơn thời gian sắp xếp một dãy các số nguyên được sắp xếp theo thứ tự ngược lại. Chúng ta có thể đo được T trong trường hợp tồi nhất tốt nhất hoặc chúng ta có thể tính được giá trị 182 trung bình của T trong tất cả các trường hợp có thể có. Cách theo trường hợp tốt nhất thường không cung cấp nhiều thòng tin lắm còn cách tính giá trị trung bình thường khó xác định hơn là cách theo trường hợp xấu nhất. Vì vậy T n thường được tính như là sự thực hiện thuật toán trong trường hợp xấu nhất của dữ liệu vào. Ta xét ví dụ sau đây Ví dụ Thuật toán sắp xếp thứ tự kiểu chọn lựa Selection Sort Algorithm Seỉection_Sort. Function Sắp xếp n số a a2 .a1 theo thứ tự tăng dần. Input n 0 và n số a a2 . an Output a . được sắp xếp tăng dần. Format SorlíanaỊ . Method 1. For i ỉ to n-1 làm các bước sau Chọn phần tử nhỏ nhất trong dãy a an 2. a. Gán giá trị i cho k 3. b. Gán giá trị aj cho min 4. c. For j i 1 to n làm các bước sau 5. If aj min tìm ra phần tử nhỏ hơn Then 6. i. Gán giá trị j vào k 7. ii. Gán giá trị aj vào min 8. d. ỉf iok phần tử nhỏ nhất khồng ở đầu dãy Then Chuyển phần tử nhỏ nhất này về đầu dãy 9. i. Gán giá trị aị
đang nạp các trang xem trước