Trong bài này, cafedev sẽ giới thiệu cho ace một số khái niệm, thuật ngữ thường được dùng trong cấu trúc dữ liệu và giải thuật, bạn cần phải biết để dễ dàng tìm hiểu về các CTDL>.
Cấu trúc dữ liệu là một cách có hệ thống để tổ chức dữ liệu nhằm sử dụng nó một cách hiệu quả. Các thuật ngữ sau đây là các thuật ngữ nền tảng của cấu trúc dữ liệu.
- Interface(giao diện) – Mỗi cấu trúc dữ liệu có một Interface(giao diện). Giao diện này đại diện cho tập hợp các hành động(phương thức) mà một cấu trúc dữ liệu có. Một giao diện(Interface) chỉ cung cấp danh sách các hành động mà nó được hỗ trợ, loại tham số mà chúng có thể chấp nhận và kiểu trả về của các hành động này.
- Triển khai(Implementation) – Việc sử dụng các cấu trúc dữ liệu với các thuật toán thông qua việc sử dụng trong các hành động của cấu trúc dữ liệu.
Nội dung chính
1. Các đặc điểm của cấu trúc dữ liệu
- Độ chính xác(Correctness) – Việc triển khai cấu trúc dữ liệu phải triển khai đúng interface(giao diện) của nó.
- Độ phức tạp về thời gian(Time Complexity) – Thời gian chạy hoặc thời gian thực hiện các hoạt động của cấu trúc dữ liệu phải càng nhỏ càng tốt.
- Độ phức tạp về không gian(Space Complexity) – Việc sử dụng bộ nhớ của một hoạt động của cấu trúc dữ liệu càng ít càng tốt.
2. Khi nào dùng cấu trúc dữ liệu
Khi các ứng dụng ngày càng phức tạp và nhiều dữ liệu, có ba vấn đề phổ biến mà các ứng dụng phải đối mặt hằng ngày.
- Tìm kiếm dữ liệu – Tìm kiếm một sản phần nào đó trong hàng tỉ tỉ dữ liệu ngày càng tăng lên dần. Khi dữ liệu phát triển, tìm kiếm sẽ trở nên chậm hơn.
- Tốc độ bộ xử lý – Tốc độ bộ xử lý mặc dù rất cao nhưng sẽ bị giới hạn nếu dữ liệu tăng lên đến hàng tỷ bản ghi dữ liệu.
- Nhiều yêu cầu – Vì hàng nghìn người dùng có thể tìm kiếm dữ liệu đồng thời trên một máy chủ web, ngay cả máy chủ nhanh cũng bị lỗi trong khi tìm kiếm dữ liệu.
Để giải quyết các vấn đề nêu trên, cấu trúc dữ liệu ra đời để giúp. Dữ liệu có thể được tổ chức theo cấu trúc dữ liệu theo cách mà tất cả các mục có thể không được yêu cầu tìm kiếm và dữ liệu cần thiết có thể được tìm kiếm gần như ngay lập tức.
3. Các trường hợp thời gian thực thi
Có ba trường hợp thường được sử dụng để so sánh thời gian thực thi của các cấu trúc dữ liệu khác nhau một cách tương đối.
- Trường hợp tồi tệ nhất(Worst Case) – Đây là trường hợp mà một hành động của cấu trúc dữ liệu cụ thể mất nhiều thời gian nhất có thể. Nếu thời gian trong trường hợp xấu nhất của một hành động là ƒ (n) thì hành động này sẽ không mất quá ƒ (n) thời gian trong đó ƒ (n) đại diện cho hàm của n.
- Trường hợp trung bình(Average Case) – Đây là kịch bản mô tả thời gian thực hiện trung bình một hành động của cấu trúc dữ liệu. Nếu một hoạt động cần ƒ (n) thời gian để thực hiện, thì m hoạt động sẽ mất mƒ (n) thời gian.
- Trường hợp tốt nhất(Best Case) – Đây là kịch bản mô tả thời gian thực thi ít nhất có thể một hành động của cấu trúc dữ liệu. Nếu một hành động mất ƒ (n) thời gian để thực hiện, thì hành động thực tế có thể mất thời gian vì số ngẫu nhiên sẽ lớn nhất là ƒ (n).
4. Các thuật ngữ cơ bản trong CTDL>
- Dữ liệu(Data) – Dữ liệu là các giá trị hoặc tập hợp các giá trị.
- Mục dữ liệu(Data Item) hay phần tử trong dữ liệu – Mục dữ liệu đề cập đến một đơn vị giá trị nào đó trong dữ liệu.
- Nhóm các mục(Group Items) hay nhóm các phần tử – Các mục dữ liệu được chia thành các mục con được gọi là Nhóm các Mục.
- Mục Cơ bản(Elementary Items) – Các mục dữ liệu không thể chia được gọi là Mục Cơ bản.
- Thuộc tính và thực thể(Attribute and Entity) – Thực thể(Entity) là một thực thể chứa các thuộc tính(Attribute) hoặc một thuộc tính nhất định, có thể được gán giá trị.
- Tập hợp các thực thể(Entity Set) – Các thực thể có các thuộc tính giống nhau tạo thành một tập hợp các thực thể.
- Trường(Field) – Trường là một đơn vị thông tin cơ bản đại diện cho một thuộc tính của một thực thể.
- Bản ghi(Record) – Bản ghi là một tập hợp các giá trị của một trường trong một thực thể nhất định.
- Tệp(File) – Tệp là một tập hợp các bản ghi của các thực thể trong một tập thực thể nhất định.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
