HỌC TIN CÙNG THỦ KHOA

Thông thường, đối với máy tính cá nhân mà chúng ta đang sử dụng thì với thuật toán với độ phức tạp O(n) chạy trong thời gian 1 giây thì giới hạn của n cỡ khoảng: n = 2*10^6. Vậy câu hỏi đặt ra, đối với thuật toán với độ phức tạp O(nlogn) chạy trong thời gian 1 giây thì giới hạn của n cỡ khoảng bao nhiêu ???

Rõ ràng, vấn đề đã cho trở thành việc giải phương trình: nlogn = 2*10^6

Ta giải phương trình trên bằng cách sử dụng trang Web: https://www.wolframalpha.com

Sau khi truy cập vào trang Web, ta gõ: n*log_2(n) = 2*10^6

Kết quả của bài toán sẽ được ghi ngay phía dưới. Hãy kích vào nút "Approximate form" để lấy kết quả chính xác

Ở đây, kết quả: n = 118.650, tức n ≈ 10^5