Bài tập  /  Bài đang cần trả lời

Trình bày và cài đặt thuật toán tìm tuyến tỉnh đối với các phần tử trên mảng hai chiều trong hai trường hợp: a) Không sử dụng phần tử “Cầm canh". b) Có sử dụng phần tử “Cầm canh”. Cho biết thời gian thực hiện của hai thuật toán trong hai trường hợp trên?

Bài 13: Trình bày và cài đặt thuật toán tìm tuyến tỉnh đối với các phần tử trên mảng hai chiều trong hai trường hợp:
a) Không sử dụng phần tử “Cầm canh".
b) Có sử dụng phần tử “Cầm canh”.
Cho biết thời gian thực hiện của hai thuật toán trong hai trường hợp trên?
1 Xem trả lời
Hỏi chi tiết
59
Tham khảo câu trả lời từ Trợ lý ảo Lazi
a) Thuật toán tìm tuyến tỉnh không sử dụng phần tử "Cầm canh":
- Đầu tiên, duyệt qua từng dòng của mảng hai chiều.
- Sau đó, duyệt qua từng phần tử trong dòng đó để tìm phần tử lớn nhất.
- Lặp lại quá trình trên cho tất cả các dòng của mảng để tìm ra phần tử lớn nhất trong mảng.

Thời gian thực hiện của thuật toán này là O(m*n), trong đó m là số hàng của mảng và n là số cột của mảng.

b) Thuật toán tìm tuyến tỉnh sử dụng phần tử "Cầm canh":
- Đầu tiên, chọn phần tử đầu tiên của mảng làm phần tử lớn nhất tạm thời.
- Duyệt qua từng phần tử của mảng, so sánh với phần tử lớn nhất tạm thời. Nếu phần tử đó lớn hơn, cập nhật phần tử lớn nhất tạm thời.
- Sau khi duyệt hết mảng, phần tử lớn nhất tạm thời sẽ là phần tử lớn nhất trong mảng.

Thời gian thực hiện của thuật toán này là O(m*n), tương tự như trường hợp không sử dụng phần tử "Cầm canh".

Tóm lại, cả hai thuật toán đều có độ phức tạp thời gian là O(m*n) trong trường hợp tìm tuyến tỉnh trên mảng hai chiều. Tuy nhiên, việc sử dụng phần tử "Cầm canh" giúp giảm số lần so sánh và cập nhật, từ đó tăng hiệu suất của thuật toán.
0
0
Tiến Nam Nguyễn
01/05 16:42:57
Trong hai trường hợp này, thời gian thực hiện của hai thuật toán là như sau:
a) Không sử dụng phần tử “Cầm canh": thời gian thực hiện là O(n2)
b) Có sử dụng phần tử “Cầm canh”: thời gian thực hiện là O(n log(n))

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường
×
Trợ lý ảo Trợ lý ảo
×
Đấu trường tri thức | Lazi Quiz Challenge +500k
Gửi câu hỏi
×