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.
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.
