Câu hỏi:

11/05/2023 185

Phân tích, trao đổi, thảo luận để tính độ phức tạp thời gian của thuật toán sắp xếp trộn.

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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).

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Đây là một ví dụ về cách viết chương trình bằng ngôn ngữ Python để trộn hai dãy số được lưu trữ trong tệp văn bản "Data.inp" và ghi kết quả vào tệp "Data.out":

Viết chương trình thực hiện công việc sau:  - Dữ liệu được nhập từ tệp văn bản Data.inp bao gồm (ảnh 1)

- Đầu tiên, chương trình sử dụng hàm open() để mở tệp "Data.inp" với chế độ đọc dữ liệu (‘r’).

- Sau đó, chương trình đọc hai dòng dữ liệu từ tệp bằng cách sử dụng phương thức readline(), và loại bỏ các ký tự trắng ở đầu và cuối dòng bằng phương thức strip().

- Tiếp theo, chương trình sử dụng phương thức split() để tách các số trong hai dòng dữ liệu thành một danh sách các số nguyên. Hàm int() được sử dụng để chuyển đổi các chuỗi số sang kiểu số nguyên.

- Sau đó, chương trình trộn hai danh sách số lại với nhau bằng cách sử dụng phương thức sorted() để sắp xếp danh sách theo thứ tự tăng dần.

- Cuối cùng, chương trình sử dụng hàm open() để mở tệp "Data.out" với chế độ ghi dữ liệu ('w'), và sử dụng phương thức write() để ghi danh sách số trộn được vào tệp. Hàm join() được sử dụng để chuyển đổi các số trong danh sách trở lại thành chuỗi, và ký tự dấu cách được sử dụng để ngăn cách giữa các số.

Lời giải

Kỹ thuật chia để trị có thể được áp dụng cho bài toán sắp xếp, và thực tế nó đã được sử dụng để thiết kế các thuật toán sắp xếp hiệu quả như QuickSort và MergeSort.

        Tuy nhiên, trong thực tế, cách tiếp cận này không phải lúc nào cũng làm tăng hiệu quả của thuật toán sắp xếp. QuickSort và MergeSort, mặc dù sử dụng phương pháp chia để trị, thường là những thuật toán có hiệu quả cao. Nhưng nếu áp dụng phương pháp chia để trị cho một thuật toán sắp xếp khác như BubbleSort hoặc InsertionSort, chẳng hạn, thì không có nhiều lợi ích. Trong những trường hợp đó, việc sử dụng phương pháp chia để trị có thể làm giảm hiệu quả của thuật toán sắp xếp.

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay