- Kỹ năng tối ưu hoá thuật toán Nguyễn Duy Hàm Tối ưu hoá là một đòi hỏi thường xuyên không chỉ trong quá trình giải quyết các bài toán tin học, mà ngay trong giải quyết các công việc thường ngày của chúng ta. - Tối ưu hoá thuật toán là một công việc yêu cầu tư duy thuật toán rất cao, cùng với khẳ năng sử dụng thuần thục các cấu trúc dữ liệu. - Lần này tôi xin được chia sẻ với các bạn về tối ưu hoá thuật toán trong giải quyết một bài toán tưởng chừng rất đơn giản, nhưng việc tìm ra thuật toán tối ưu cho nó lại không dễ chút nào. - Tối ưu hoá thường được tiến hành theo 2 góc độ đó là tối ưu theo không gian có nghĩa là tối ưu không gian lưu trữ (bộ nhớ), và tối ưu theo thời gian có nghĩa là giảm độ phức tạp thuật toán, giảm các bước xử lý trong chương trình…Tuy nhiên không phải lúc nào ta cũng có thể đạt được đồng thời cả 2 điều đó, trong nhiều trường hợp tối ưu về thời gian sẽ làm tăng không gian lưu trữ, và ngược lại. - Với các bài toán có hạn chế về thời gian như thế, đòi hỏi ta phải đưa ra được thuật toán tối ưu nhất. - Thuật toán trên sử dụng 2 vòng lặp lồng nhau, vòng đầu tiên lặp n lần, vòng thứ 2 lặp tối đa n lần, nên dễ thấy độ phức tạp của thuật toán này là O(n2). - Ta sử dụng thêm 2 mảng k,c mỗi mảng gồm n phần tử. - Với thuật toán trên độ phức tạp là O(n) với chỉ 1 vòng lặp n lần duy nhất. - Như vậy, có thể nói ta đã tối ưu xong về mặt thời gian từ độ phức tạp O(n3) xuống còn O(n)