tailieunhanh - GIÁO TRINH TOÁN RỜI RẠC - CHƯƠNG I: THUẬT TOÁN_2

Để tìm số nguyên x trong bảng liệt kê a1,a2,.,an với a1 | CHƯƠNG I THUẬT TOÁN Để tìm số nguyên x trong bảng liệt kê a1 a2 . an với ai a2 . an ta bắt đầu bằng việc so sánh x với số hạng am ở giữa của dãy với m n 1 2 . Nếu x am việc tìm kiếm x giới hạn ở nửa thứ hai của dãy gồm am 1 am 2 . an. Nếu x không lớn hơn am thì sự tìm kiếm giới hạn trong nửa đầu của dãy gồm a1 a2 . am. Bây giờ sự tìm kiếm chỉ giới hạn trong bảng liệt kê có không hơn n 2 phần tử. Dùng chính thủ tục này so sánh x với số hạng ở giữa của bảng liệt kê được hạn chế. Sau đó lại hạn chế việc tìm kiếm ở nửa thứ nhất hoặc nửa thứ hai của bảng liệt kê. Lặp lại quá trình này cho tới khi nhận được một bảng liệt kê chỉ có một số hạng. Sau đó chỉ còn xác định số hạng này có phải là x hay không. Giả mã cho thuật toán tìm kiếm nhị phân được cho dưới đây procedure tìm kiếm nhị phân x integer a1 a2 . an integers tăng dần i 1 i là điểm mút trái của khoảng tìm kiếm j n j là điểm mút phải của khoảng tìm kiếm while i j begin m i j 2 if x am then i m 1 else j m end if x ai then location i else location 0 location là chỉ số dưới của số hạng bằng x hoặc 0 nếu không tìm thấy x . ĐỘ PHỨC TẠP CỦA THUẬT TOÁN. . Khái niệm về độ phức tạp của một thuật toán Thước đo hiệu quả của một thuật toán là thời gian mà máy tính sử dụng để giải bài toán theo thuật toán đang xét khi các giá trị đầu vào có một kích thước xác định. Một thước đo thứ hai là dung lượng bộ nhớ đòi hỏi để thực hiện thuật toán khi các giá trị đầu vào có kích thước xác định. Các vấn đề như thế liên quan đến độ phức tạp tính toán của một thuật toán. Sự phân tích thời gian cần thiết để giải một bài toán có kích thước đặc biệt nào đó liên quan đến độ phức tạp thời gian của thuật toán. Sự phân tích bộ nhớ cần thiết của máy tính liên quan đến độ phức tạp không gian của thuật toán. Vệc xem xét độ phức tạp thời gian và không gian của một thuật toán là một vấn đề rất thiết yếu khi các thuật toán được thực hiện. Biết một thuật toán sẽ đưa ra đáp số trong một micro giây trong một phút hoặc trong một tỉ năm hiển nhiên là