Cấu trúc dữ liệu & Thuật toán - Tổng quan
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- Mỗi cấu trúc dữ liệu có một giao diện. Giao diện đại diện cho tập hợp các hoạt động mà một cấu trúc dữ liệu hỗ trợ. Một giao diện chỉ cung cấp danh sách các hoạt động được hỗ trợ, loại tham số mà chúng có thể chấp nhận và loại trả về của các hoạt động này.
Implementation- Việc thực hiện cung cấp sự biểu diễn bên trong của một cấu trúc dữ liệu. Việc triển khai cũng cung cấp định nghĩa của các thuật toán được sử dụng trong các hoạt động của cấu trúc dữ liệu.
Đặc điểm của cấu trúc dữ liệu
Correctness - Việc triển khai cấu trúc dữ liệu nên thực hiện đúng giao diện của nó.
Time Complexity - Thời gian chạy hoặc thời gian thực hiện các thao tác của cấu trúc dữ liệu phải càng nhỏ càng tốt.
Space Complexity - Sử dụng bộ nhớ của một hoạt động cấu trúc dữ liệu càng ít càng tốt.
Cần 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 ngay bây giờ.
Data Search- Xem xét số lượng hàng tồn kho 1 triệu (10 6 ) mặt hàng của một cửa hàng. Nếu ứng dụng để tìm kiếm một mục, nó phải tìm kiếm một mục trong 1 triệu (10 6 ) mục mỗi khi làm chậm tìm kiếm. Khi dữ liệu phát triển, tìm kiếm sẽ trở nên chậm hơn.
Processor speed - 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.
Multiple requests - 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, thậm chí máy chủ nhanh bị lỗi khi đang 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ải cứu. 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.
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.
Worst Case- Đây là tình huống mà một hoạt động 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 hoạt động là ƒ (n) thì hoạt động này sẽ không mất quá ƒ (n) thời gian trong đó ƒ (n) đại diện cho hàm của n.
Average Case- Đây là kịch bản mô tả thời gian thực hiện trung bình của một hoạt động của một 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.
Best Case- Đây là kịch bản mô tả thời gian thực thi ít nhất có thể của một hoạt động của cấu trúc dữ liệu. Nếu một hoạt động mất ƒ (n) thời gian để thực hiện, thì hoạt động thực tế có thể mất thời gian vì số ngẫu nhiên sẽ lớn nhất là ƒ (n).
Thuật ngữ cơ bản
Data - Dữ liệu là các giá trị hoặc tập giá trị.
Data Item - Mục dữ liệu đề cập đến một đơn vị giá trị.
Group Items - Các mục dữ liệu được chia thành các mục con được gọi là Mục nhóm.
Elementary Items - Các mục dữ liệu không thể phân chia được gọi là Mục cơ bản.
Attribute and Entity - Thực thể là thực thể chứa các thuộc tính hoặc thuộc tính nhất định, có thể được gán giá trị.
Entity Set - Các thực thể có thuộc tính giống nhau tạo thành một tập thực thể.
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ể.
Record - Bản ghi là tập hợp các giá trị trường của một thực thể nhất định.
File - Tệp là 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.