Video: Lộ trình học Cấu Trúc Dữ Liệu & Giải Thuật? Học gì để đi thực tập? 2025
Hãy tưởng tượng cố gắng để tìm một mục trong một danh sách mà không phân loại nó trước tiên. Mỗi tìm kiếm trở thành một tìm kiếm tuần tự tốn nhiều thời gian. Tuy nhiên, một trường hợp có thể được thực hiện không phân loại dữ liệu cho các thuật toán. Sau khi tất cả, dữ liệu vẫn có thể truy cập, ngay cả khi bạn không sắp xếp nó - và phân loại cần có thời gian.
Tất nhiên, vấn đề với dữ liệu chưa được phân loại là vấn đề tương tự như ngăn kéo rác trong nhà bếp của bạn (hoặc bất cứ nơi nào bạn có ngăn kéo rác của bạn - giả định rằng bạn có thể tìm thấy nó ở tất cả). Tìm kiếm bất cứ thứ gì trong ngăn kéo rác tốn rất nhiều thời gian vì bạn thậm chí không thể bắt đầu đoán nơi tìm thấy thứ gì đó. Thay vì chỉ cần tiếp cận và lấy những gì bạn muốn, bạn phải đưa ra vô số những thứ khác mà bạn không muốn trong một nỗ lực để tìm thấy một mục bạn cần. Thật không may, mặt hàng bạn cần không có trong ngăn kéo rác ở nơi đầu tiên-bạn có thể đã ném nó ra hoặc đặt nó trong một ngăn kéo khác nhau.
ngăn kéo rác trong nhà của bạn giống như dữ liệu chưa được sắp xếp trên hệ thống của bạn. Khi dữ liệu không được phân loại, bạn cần phải tìm kiếm một mục cùng một lúc và thậm chí bạn không biết liệu bạn sẽ tìm thấy những gì bạn cần mà không cần tìm kiếm mọi mục trong tập dữ liệu trước tiên. Đó là một cách rất bực bội để làm việc với dữ liệu.
Tất nhiên, chỉ cần phân loại dữ liệu là không đủ. Nếu bạn có một cơ sở dữ liệu nhân viên được sắp xếp theo họ, nhưng vẫn cần phải tìm kiếm nhân viên theo ngày sinh, việc sắp xếp không hữu ích. (Giả sử bạn muốn tìm tất cả nhân viên có ngày sinh nhật vào một ngày nào đó.) Để tìm ngày sinh bạn cần, bạn vẫn phải tìm toàn bộ bộ dữ liệu một mục một lần. Do đó, phân loại phải tập trung vào một nhu cầu cụ thể. Vâng, bạn cần cơ sở dữ liệu nhân viên được phân loại theo bộ phận tại một thời điểm và theo tên cuối cùng vào thời điểm khác, nhưng bây giờ bạn cần nó được sắp xếp theo ngày sinh để sử dụng tập dữ liệu có hiệu quả.
Cần duy trì một số đơn đặt hàng được sắp xếp cho cùng một dữ liệu là lý do mà các nhà phát triển tạo ra các chỉ mục. Sắp xếp một chỉ mục nhỏ nhanh hơn phân loại toàn bộ tập dữ liệu. Chỉ mục duy trì một trật tự dữ liệu cụ thể và trỏ đến tập dữ liệu đầy đủ để bạn có thể tìm thấy những gì bạn cần cực kỳ nhanh. Bằng cách duy trì một chỉ mục cho mỗi yêu cầu sắp xếp, bạn có thể cắt giảm thời gian truy cập dữ liệu một cách hiệu quả và cho phép nhiều người truy cập dữ liệu vào cùng một thời điểm theo thứ tự mà họ cần truy cập.
Có nhiều cách để phân loại thuật toán phân loại. Một trong những cách này là tốc độ của loại. Khi xem xét mức độ hiệu quả của một thuật toán sắp xếp đặc biệt ở sắp xếp dữ liệu, thời gian chuẩn sẽ xem xét hai nhân tố:
- So sánh: Để di chuyển dữ liệu từ một vị trí trong một bộ dữ liệu sang một, bạn cần phải biết vị trí di chuyển nó, có nghĩa là so sánh dữ liệu đích với dữ liệu khác trong tập dữ liệu.Có ít so sánh hơn có nghĩa là hiệu suất tốt hơn.
- Sở giao dịch: Tùy thuộc vào cách bạn viết một thuật toán, dữ liệu có thể không đến được vị trí cuối cùng trong tập dữ liệu trong lần thử đầu tiên. Dữ liệu có thể thực sự di chuyển nhiều lần. Số lần trao đổi ảnh hưởng đến tốc độ đáng kể bởi vì bây giờ bạn đang chuyển dữ liệu từ vị trí này sang vị trí khác trong bộ nhớ. Sự trao đổi ít hơn và nhỏ hơn (chẳng hạn như khi sử dụng các chỉ số) có nghĩa là hoạt động tốt hơn.
