Tổng quan về cấu trúc dữ liệu & thuật toán  

Cấu trúc dữ liệu là một cách có hệ thống để tổ chức dữ liệu để sử dụng nó một cách hiệu quả. Các thuật ngữ sau đây là các điều khoản nền tảng của một cấu trúc dữ liệu.

• Giao diện - 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 phép tính mà cấu trúc dữ liệu hỗ trợ. Một giao diện chỉ cung cấp danh sách các phép tính được hỗ trợ, loại tham số có thể chấp nhận và trả về loại của các phép tính này.
• Triển khai - Triển khai cung cấp biểu diễn bên trong của cấu trúc dữ liệu. Việc thực hiện cũng cung cấp định nghĩa về các thuật toán được sử dụng trong các phép tính của cấu trúc dữ liệu.

Đặc điểm của một cấu trúc dữ liệu

• Tính chính xác - Việc thực hiện cấu trúc dữ liệu phải thực hiện đúng giao diện của nó.
• Độ phức tạp thời gian - Thời gian chạy hoặc thời gian thực hiện các phép tính của cấu trúc dữ liệu phải càng ngắn càng tốt.
• Dung lượng sử dụng bộ nhớ - Việc sử dụng bộ nhớ của một phép tính cấu trúc dữ liệu nên càng ít càng tốt.

Tại sao cấu trúc dữ liệu là cần thiết?

Ngày nay, khi các ứng dụng ngày càng phức tạp và lượng dữ liệu ngày càng lớn, có ba vấn đề phổ biến mà các ứng dụng phải đối mặt

Tìm kiếm dữ liệu – Giả sử có 1 triệu mặt hàng được lưu trữ trong kho hàng. Và giả sử có một ứng dụng để tìm kiếm một mặt hàng trong đó. Như vậy, mỗi khi thực hiện tìm kiếm, nó sẽ phải tìm kiếm một mặt hàng trong 1 triệu, điều này sẽ ngày càng chậm hơn khi dữ liệu tăng lên.

Tốc độ của bộ xử lý - Tốc độ của bộ xử lý mặc dù rất cao, nhưng nếu dữ liệu tăng lên hàng tỷ bản ghi tốc độ xử lý sẽ không còn nhanh được nữa.

Đa yêu cầu – Khi hàng ngàn người dùng thực hiện việc tìm kiếm dữ liệu đồng thời trên một máy chủ web thì cho dù máy chủ đó có nhanh đến mấy thì cũng bị chậm đi trong khi tìm kiếm dữ liệu.

Để giải quyết các vấn đề nêu trên, các cấu trúc dữ liệu đến như một giải pháp thực thụ. Dữ liệu có thể được sắp xếp theo cấu trúc dữ liệu theo cách để khi thực hiện tìm kiếm một phần tử nào đó thì dữ liệu yêu cầu sẽ được tìm thấy ngay lập tức.

Thời gian thực hiện

Có ba trường hợp thường được sử dụng để so sánh thời gian thực hiện của cấu trúc dữ liệu khác nhau theo cách tương đối.

• Trường hợp xấu nhất - Đây là tình huống trong đó một phép tính cấu trúc dữ liệu cụ thể mất thời gian tối đa có thể. Nếu thời gian trường hợp xấu nhất của một phép tính là ƒ (n) thì phép tính này sẽ không mất nhiều hơn (n) thời gian trong đó ƒ (n) đại diện cho chức năng của n.
• Trường hợp trung bình - Đây là kịch bản mô tả thời gian thực hiện trung bình của một phép tính của cấu trúc dữ liệu. Nếu một phép tính mất (n) thời gian thực hiện, thì m phép tính sẽ mất mƒ (n) thời gian.
• Trường hợp tốt nhất - Đây là kịch bản mô tả thời gian thực hiện ít nhất có thể của một phép tính của cấu trúc dữ liệu. Nếu một phép tính mất (n) thời gian thực hiện, thì phép tính thực tế có thể mất thời gian là số ngẫu nhiên sẽ tối đa là (n).

Các thuật ngữ cơ bản

• Dữ liệu - Dữ liệu là các giá trị hoặc tập hợp các giá trị.
• Mục dữ liệu - Mục dữ liệu đề cập đến một đơn vị giá trị.
• Các mục nhóm - Các mục dữ liệu được chia thành các mục phụ được gọi là mục nhóm.
• Các mục sơ cấp - Các mục dữ liệu không thể phân chia được gọi là mục sơ cấp.
• Thuộc tính và thực thể - Một 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 các giá trị.
• Tập thực thể - Các thực thể của các thuộc tính tương tự tạo thành một tập thực thể.
• Trường - Trường là một đơn vị thông tin cơ bản duy nhất đại diện cho một thuộc tính của thực thể.
• Bản ghi - Bản ghi là tập hợp các giá trị trường của một thực thể nhất định.
• Tệp - 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.

- Hiếu Kiều -