Chọn thuật toán gợi ý sản phẩm nhanh nhất cho sàn TMĐT ShopVN

Ban kỹ thuật ShopVN thu thập mô tả cấu trúc của một số thuật toán ứng viên dưới dạng mã hoá đơn giản như sau (mỗi thuật toán gắn với một giá trị n là số người dùng cần xử lý trong lần kiểm thử):

• loai = 1: chương trình chỉ có một vòng lặp for đơn (giống Chương trình 1 đã học), với hàm thời gian T(n) = n + 3, độ phức tạp O(n).
• loai = 2: chương trình có hai vòng lặp for lồng nhau (giống Chương trình 2 đã học), với hàm thời gian T(n) = n*n + 3, độ phức tạp O(n^2).
• loai = 3: chương trình có một vòng lặp while với biến điều khiển nhân đôi mỗi bước (giống bài luyện tập vòng lặp nhân đôi), số bước lặp là số lần nhân đôi cho tới khi vượt n, hàm thời gian T(n) = 3*(số bước lặp) + 4, độ phức tạp O(logn).

Em hãy viết chương trình Python thực hiện:

1. Đọc số nguyên k (số thuật toán ứng viên cần so sánh, 1 ≤ k ≤ 5).
2. Đọc tiếp k dòng, mỗi dòng gồm hai số nguyên loai và n cách nhau bởi dấu cách (loai thuộc tập {1, 2, 3}).
3. Với mỗi thuật toán, tính đúng T(n) theo công thức tương ứng ở trên và in ra một dòng theo đúng định dạng: Thuat toan i: T(n) = <giá trị>, do phuc tap <O(...)> (i là số thứ tự thuật toán tính từ 1).
4. Sau khi in xong k dòng trên, dựa vào bậc O-lớn (không dựa vào giá trị T(n) cụ thể), xác định thuật toán có độ phức tạp thời gian THẤP NHẤT (nhanh nhất khi n tiến tới vô cùng, thứ tự ưu tiên: O(logn) nhỏ hơn O(n) nhỏ hơn O(n^2)); nếu có nhiều thuật toán cùng bậc thấp nhất thì chọn thuật toán xuất hiện đầu tiên. In dòng cuối cùng theo đúng định dạng: Thuat toan nhanh nhat: Thuat toan x (x là số thứ tự thuật toán được chọn).

Input: dòng đầu là k; k dòng tiếp theo, mỗi dòng gồm hai số nguyên loai và n cách nhau bởi dấu cách.

Output: k dòng mô tả T(n) và độ phức tạp, tiếp theo là 1 dòng xác định thuật toán nhanh nhất.