Chào mọi người mình hiện đang tìm hiểu về thuật toán nên trong quá trình tìm hiểu có 1 chút băn khoăn, thắc mắc mà mình chưa thể nghĩ ra được nên mình post bài này hi vọng mọi người giúp dùm. Tạm thời mình có 3 câu hỏi sau: 1/Xem xét bài toán xác định xem 1 dãy số tùy ý n con số <x1, x2, ..., xn> có chứa các lần xuất hiện lặp lại của 1 con số nào đó hay không. Dẫn chứng rằng điều này có thể thực hiện theo thời gian theta(nlgn). Có thể mình dùng ký hiệu khác các bạn không biết nên mình giải thích về theta(nlgn) như sau: ví dụ thời gian thực hiện 1 bài toán được biểu diễn là T(n)=a*n^2+b*n+c thì mình viết là T(n)=theta(n^2). 2/Làm sao để sửa đổi hầu hết mọi thuật toán để có 1 thời gian thực hiện tốt trong trường hợp tốt nhất? 3/Dùng phép quy nạp toán học để nêu rõ nghiệm của phép truy toán: T(n)=2, nếu n=2 T(n)=2*T(n/2)+n, nếu n>2^k,k>1 là T(n)=n*lgn.
À riêng câu 3 thì mình cuối cùng cũng đã giải được rồi cho nên mong các bạn giúp dùm câu 1 và câu 2 nha. p/s: mình post bài ờ box này vì thấy thuật toán với lập trình rất liên quan với nhau đấy chứ. Còn nếu lộn box thì nhờ ai đó move qua dùm ^_^
