Anonymous
0
0
Xét bài toán: Cho danh sách các số nguyên 4-4, a,,..., a ) khác nhau từng đôi một
- asked 4 months agoVotes
0Answers
0Views
Giải SBT Tin học 11 Bài 5: Đánh giá thuật toán
1) O(nlogn).
2) O(n).
Lời giải:
1) Sắp xếp lại danh sách theo thứ tự giảm dần bằng phương pháp sắp xếp nhanh (hàm Sorted ( ) có độ phức tạp O(n.log,n )) rồi in ra phần tử ở vị trí thứ hai.
2) Khởi tạo hai biến max1 = 0 và max2 = 0 tượng trưng cho giá trị lớn thứ 0 nhất và lớn thứ hai trong danh sách A, ta tiến hành duyệt và xét lần lượt từng phần tử v của A:
Nếu max1 < v, ta cập nhật max2 = max1 và max1 = v.
Ngược lại, ta có thể suy ra max1>v(max1 không thể bằng v vì các phần tử trong danh sách A khác nhau từng đôi một). Ta so sánh max2 và v. Nếu max2 < v thì ta cập nhật max2 = v.