Cài đặt: Tìm min max của 1 dãy n số với độ phức tạp thuật toán là 3n/2

Xem vấn đề tại đây

Code C:

Continue reading “Cài đặt: Tìm min max của 1 dãy n số với độ phức tạp thuật toán là 3n/2”

Advertisements

Tìm min max của 1 dãy n số với độ phức tạp thuật toán là 3n/2

Thông thường với bài toán đơn giản này chúng ta mất 1 vòng lặp, mỗi lần lặp cần 2 phép so sánh, vị chi là 2n phép so sánh. Tuy nhiên, có cách mà chỉ mất 3n/2 phép so sánh. Thật vậy, chú ý rằng để tìm min max 2 số ta chỉ cần 1 phép so sánh, tìm min max của dãy n số (a1, a2, a3, … an) theo cách như sau:

Xét n/2 nhóm 2 số sau: (a1, a2); (a3, a4); (a5, a6); … để tìm min max của hết mỗi nhóm cần n/2 phép so sánh. Đánh số các nhóm này là: b1, b2, …, b[n/2]. Lúc này ở mỗi nhóm ta đều biết min và max của nhóm đó.

Lại chia nhóm tiếp: (b1, b2); (b3, b4); (b5, b6); …n/4 nhóm, để tìm min max của mỗi nhóm ta cần 2 phép so sánh (1 phép cho 2 min, 1 phép cho 2 max). Tổng cộng là 2 * (n/4) = n/2 phép so sánh.

Lặp lại quá trình trên, ta có số các phép so sánh tiếp theo tính được là n/4, n/8, n/16, n/32, …

Tổng số phép so sánh là: n/2 + n/2 + n/4 + n/8 + n/16 + n/32 + … dễ thấy = 3n/2. Đây chỉ là 1 phép tính giới hạn (lim) đơn giản.