Cấu trúc dữ liệu và giải thuật - Bài 1: Tổng quan

Lưu ý: Các ví dụ và giải thuật trong các bài viết mình sẽ trình bày bằng ngôn ngữ lập trình C, vậy nên các bạn nên hiểu cơ bản về ngôn ngữ lập trình này. Mình dùng phần mềm Dev-C++, đây là phần mềm rất phổ biến để lập trình ngôn ngữ C, ngoài ra các bạn có thể dùng Codeblocks hoặc Visual Studio (phiên bản qua các năm) của Microsoft,...

Cấu trúc dữ liệu là hệ thống các phương pháp các thức tổ chức lưu trữ và sắp xếp dữ liệu để sử dụng chúng một cách hiệu quả nhất. Các thuật ngữ nền tảng của một cấu trúc dữ liệu:

Giao diện (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 thông số chúng có thể chấp nhận và trả về kiểu hoạt động này.

Thực hiện (Implementation): Thực hiện cung cấp các đại diện nội bộ của một cấu trúc dữ liệu. Thực hiện cũng cung cấp các đị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.

Tính đặc thù của một cấu trúc dữ liệu

Tính đúng đắn, chính xác: 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ó.

Thời gian phức tạp: Thời gian chạy hay thời gian thực thi hoạt động của một cấu trúc dữ liệu là nhỏ nhất có thể.

Độ phức tạp không gian nhớ (không gian lưu trữ): Bộ nhớ (không gian nhớ) được sử dụng cho một hoạt động của một cấu trúc dữ liệu là nhỏ nhất có thể.

Sự cần thiết của một cấu trúc dữ liệu

Khi một ứng dụng phức tạp và sử dụng nhiều dữ liệu, có 3 vấn đề chung mà ứng dụng cần giải quyết:

Tìm kiếm dữ liệu: Giả sử ứng dụng cần tìm một bản ghi trong 10 triệu bản ghi sẵn có mỗi khi thực thi một hoạt động tìm kiếm, nếu dữ liệu tăng lên thì thời gian tìm kiếm cũng tăng dẫn tới hiệu suất không cao.

Tốc độ xử lý: Nếu tốc độ xử lý có thể cao nhưng vẫn có giới hạn nếu dữ liệu tăng lên hàng tỷ bản ghi.

Xử lý nhiều yêu cầu: Hàng nghìn người dùng đồng thời cùng tìm kiếm trên máy chủ, nếu không xử lý tốt thì có thể sẽ bị sập.

Khái niệm 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 hiện các cấu trúc dữ liệu khác nhau một cách tương đối.

Tồi nhất (Worst Case): Đây là trường hợp mà một thao tác cơ cấu dữ liệu cụ thể mất thời gian tối đa mà nó có thể thực hiện. Nếu thời gian trường hợp xấu nhất của hoạt động là ƒ(n) thì thao tác này sẽ không mất nhiều hơn ƒ(n) thời gian, trong đó ƒ(n) đại diện cho hàm của n. Ký hiệu là O(f(n)) (đọc là O lớn f(n)).

Trung bình (Average Case): Đây là trường hợp mô tả thời gian thực hiện trung bình của hoạt động của một 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ì m hoạt động sẽ mất mƒ(n) thời gian. Ký hiệu là Θ(f(n)) (đọc là Theta f(n)).

Tốt nhất (Best Case): Đây là kịch bản mô tả thời gian thực hiện ít nhất có thể 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 mất thời gian thực hiện ƒ(n) thì hoạt động thực tế có thể mất thời gian vì số ngẫu nhiên tối đa là ƒ(n). Ký hiệu là 𝝮(f(n)) (đọc là Omage f(n)).

Cơ bản về thuật toán

Thuật toán là một thủ tục bao gồm một dãy hữu hạn các bước thực hiện để nhận được kết quả đầu ra từ đầu vào của bài toán. Một thuật toán thường không phụ thuộc vào ngôn ngữ lập trình mà nó có thể được triển khai với các ngôn ngữ lập trình khác nhau.

Đặc trưng của một thuật toán:

Không mơ hồ (Unambiguous): Một thuật toán phải rõ ràng và không mơ hồ. Mỗi bước hoặc giai đoạn của một thuật toán, dữ liệu đầu vào/đầu ra phải rõ ràng và những chỉ dẫn chỉ mang một ý nghĩa nhất định.

Đầu vào (Input): Một thuật toán có 0 hoặc nhiều các đầu vào được định nghĩa.

Đầu ra (Output): Một thuật toán có 1 hoặc nhiều hơn các đầu ra được định nghĩa và phải phù hợp với yêu cầu đầu ra.

Hữu hạn (Finiteness): Thuật toán phải kết thúc đưa được dữ liệu đầu ra sau một số hữu hạn các bước.

Khả dụng (Feasibility): Thuật toán cần phù hợp và khả dụng với các nguồn tài nguyên hiện có.

Độc lập (Independent): Với các bước được đưa ra của thuật toán có thể được thực thi với nhiều ngôn ngữ khác nhau.

Tổng quát (Generality): Thuật toán có thể áp dụng giải các bài toán có dạng đã cho.

Viết một thuật toán thế nào?

Không có một định nghĩa tiêu chuẩn về viết thuật toán, đúng hơn là còn phụ thuộc vào vấn đề và tài nguyên hiện có. Thuật toán không bao giờ viết chi tiết hỗ việc viết mã lập trình.

Thuật toán được viết đưa ra các hướng dẫn để giải quyết bài toán nhưng không phải tất cả các trường hợp. Thuật toán được viết khi bài toán đã được đinh nghĩa rõ ràng, một bài toán có thể được thiết kế với nhiều phương hướng giải quyết khác nhau. Ví dụ thuật toán cho bài toán công hai số nguyên.

Bước 1: Khai báo 3 số nguyên a, b, c

Bước 2: Gắn giá trị a, b

Bước 3: Cộng giá trị a và b

Bước 4: Lưu trữ giá trị vừa cộng ở bước trên vào c

Bước 5: Đưa ra giá trị c

Khi phân tích thiết kế thuật toán cần chú ý đến: Độ ưu tiên, thứ tự giải trước sau, tài nguyên hiện có (không gian nhớ, thời gian thực thi thuật toán), tối ưu thuật toán, phương pháp giải quyết vấn đề khả dụng nhất.

Một số kỹ thuật phân tích thuật toán

Phân tích cấu trúc tuần tự

Giả sử A và B là hai đoạn của thuật toán, có thể là câu lệnh, cũng có thể là một thuật toán con. Định nghĩa Time(A), Time(B) là thời gian tính lần lượt của A và B. Khi đó thời gian đòi hỏi tính A và B là:

Time (A, B) = Time(A) + Time(B)

Nói cách khác, thời gian thực thi của một thuật toán bằng tổng thời gian thực thi của các đoạn thuật toán con. Thời gian thực thi trung bình sẽ là:

Time(A,B) = 𝚯(max(Time(A), Time(B)))

Phân tích vòng lặp for

Giả sử ta có vòng lặp for như sau:

for (i=0; t<n; i++) {

A(i); // hàm A(i) sẽ làm gì đó

}

Khi đó thời gian thực hiện hàm A(i) là t(i) và thời gian thực hiện vòng lặp trên sẽ là: i=0nt(i) = n.t(i). Vậy thời gian tính trung bình của vòng lặp trên sẽ là 𝚯(n) (t(i) là thời gian cụ thể và là một hằng số).

Câu lệnh đặc trưng

Câu lệnh đặc trưng là câu lệnh được thực hiện thường xuyên ít nhất là cũng như bất kỳ câu lệnh nào trong thuật toán.

Ví dụ:

int sum = 0;

for (i=0; t<n; i++) {

// có lệnh gì đó ở đây

for (j=0; j<n; j++) {

sum += a[i][j];

// có lệnh gì đó ở đây

}

}

Chọn câu lệnh đặc trưng là sum+=a[i][j], câu lệnh này mất thời gian t để thực hiện xong. Vòng lặp trong cùng sẽ mất n.t thời gian thực thi, ra vòng lặp ngoài sẽ mất thời gian n.n.t thời gian thực thi hay bằng t.n2. Vậy ta có thời gian thực thi trung bình của đoạn lệnh là 𝚯(n2) (t là hằng số).

Các ký hiệu tiệm cận thông thường

Hằng số (constant): O(1)

Logarithmic: O(log n)

Tuyến tính (Linear): O(n)

Trên tuyến tính (superlinear): O(n log n)

Bình phương (quadratic): O(n2)

Bậc ba (cubic): O(n3)

Hàm mũ (exponential): 2O(n)

Đa thức (polynomial): nO(1)