Cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu và giải thuật
Ai cũng thuộc lòng rằng sắp xếp nhanh là O(n log n) và sắp xếp nổi bọt là O(n²). Rất ít người từng đếm thử xem trên đúng mảng của mình thì hai cái đó chênh nhau bao nhiêu phép, và ở kích thước nào thì cái chậm hơn lại ít phép hơn.
Môn này viết cho sinh viên năm 2, sau khi đã biết viết vòng lặp, hàm và mảng ở Lập trình C hoặc Java.
Cách môn này khác sách giáo khoa
Sách dạy ký hiệu O trước rồi mới nói thuật toán. Ở đây ngược lại: chạy thuật toán trên dữ liệu bạn đặt, đếm từng phép, rồi mới đặt tên cho dáng của con số.
Lý do rất cụ thể. Ký hiệu O là một phép trừu tượng hoá cố ý làm mất thông tin: nó bỏ hệ số, bỏ hằng số cộng, và chỉ nói chuyện gì xảy ra khi n lớn. Điều đó hữu ích, nhưng nó giấu đi phần lớn những gì bạn cần biết khi ngồi trước một bài toán thật:
- Sắp xếp chèn và sắp xếp chọn cùng là
O(n²), nhưng trên một mảng đã sắp thì cái đầu tốnn − 1phép so sánh còn cái sau vẫn tốnn(n−1)/2. Với 12 phần tử là 11 so với 66. 100nvàn²cắt nhau ởn = 100. Dưới mốc đó thì cáiO(n²)ít phép hơn, và rất nhiều mảng trong đời thật nằm dưới mốc đó.- Tìm nhị phân cần mảng đã sắp. Nếu bạn chỉ tìm một lần thì sắp trước rồi tìm nhị phân đắt hơn quét tuyến tính. Số lần tìm tối thiểu để nó có lãi là một con số cụ thể, và bạn tính được nó.
Mỗi bài ở đây là một bảng tính sống. Bạn đổi dữ liệu, đổi kích thước, đổi tham số, và con số tính lại ngay. Mọi phép đếm đều bị một cổng kiểm số canh, nên nếu sim nói mảng này tốn 66 phép so sánh thì nó thật sự tốn đúng 66.
Ba điều phải nói trước
Đếm phép tính không phải đo thời gian chạy. Một phép so sánh chuỗi đắt hơn một phép so sánh số. Bộ nhớ đệm của máy làm mọi dự đoán lệch, và trên mảng nhỏ thì quét tuyến tính thường nhanh hơn tìm nhị phân thật, dù nó tốn nhiều phép hơn. Sim đếm phép, nó không đo giây.
Mọi dữ liệu ngẫu nhiên đều có hạt giống. Không sim nào ở đây gọi hàm ngẫu nhiên của trình duyệt. Cùng một hạt giống thì luôn cùng một dãy số, nên con số bạn thấy hôm nay và con số bạn thấy tuần sau là một, và cổng kiểm được điều đó.
Ranh giới của từng bài được nói thẳng trong bài. Chỗ nào sim chứng minh được thì nó nói là chứng minh, chỗ nào chỉ là quy ước hay là kết quả thực nghiệm của người khác thì nó nói đúng như vậy.
Môn này nằm ở đâu
Phần duyệt đồ thị (BFS, DFS, A*, đường đi ngắn nhất) đã được dạy kỹ ở Trí tuệ nhân tạo dưới góc nhìn tìm kiếm lời giải, nên môn này không dạy lại; khi tới chương đồ thị nó nói về chi phí biểu diễn và liên kết chéo sang đó.
Cần ôn con trỏ và cấp phát động thì xem Lập trình C. Muốn thấy cấu trúc dữ liệu đã đóng gói sẵn trong thư viện thì xem tập hợp trong Java.