Quảng cáo
1 câu trả lời 87
Gọi T(n) là thời gian chạy của thuật toán sắp xếp trộn.
Với n = 1, dòng lệnh 2 trả lại ngay dãy gốc A, do đó T(1) = 1.
Trường hợp tổng quát
- Tại bước chia (dòng 5), cần O(1) thời gian để thực hiện.
- Các dòng 6, 7 sẽ mất 2T(n/2) thời gian.
- Dòng lệnh 8 thực hiện trộn hai dãy với thời gian O(n).
Tổng kết lại chúng ta các công thức sau tính thời gian T(n).
T(1)=1
T(n) = 2T(n/2) + O(n), n > 1 (1)
Không mất tổng quát, giả sử tồn tại hằng số C > 0 sao cho:
T(n) = 2T (n/2)+ Cn, n > 1 (2)
Các công thức (1), (2) được gọi là công thức truy hồi để tính độ phức tạp thời gian T(n)
của thuật toán trộn.
Người ta tính được: T(n) = O(nlogn).
Quảng cáo
Bạn cần hỏi gì?
Câu hỏi hot cùng chủ đề
-
Đã trả lời bởi chuyên gia
86252
