Cấu trúc dữ liệu - Khái niệm cơ bản về thuật toán

Thuật toán là một thủ tục từng bước, xác định một tập hợp các lệnh được thực hiện theo một thứ tự nhất định để có được đầu ra mong muốn. Các thuật toán thường được tạo độc lập với các ngôn ngữ cơ bản, tức là một thuật toán có thể được thực hiện bằng nhiều ngôn ngữ lập trình.

Từ quan điểm cấu trúc dữ liệu, sau đây là một số loại thuật toán quan trọng:

• Search - Thuật toán tìm kiếm một mục trong cấu trúc dữ liệu.

• Sort - Thuật toán sắp xếp các mặt hàng theo một thứ tự nhất định.

• Insert - Thuật toán chèn mục trong cấu trúc dữ liệu.

• Update - Thuật toán cập nhật một mục hiện có trong cấu trúc dữ liệu.

• Delete - Thuật toán xóa một mục hiện có khỏi cấu trúc dữ liệu.

Đặc điểm của một thuật toán

Không phải tất cả các thủ tục đều có thể được gọi là một thuật toán. Thuật toán phải có các đặc điểm sau:

• Unambiguous- Thuật toán phải rõ ràng và không mập mờ. Mỗi bước (hoặc giai đoạn) của nó, và đầu vào / đầu ra của chúng phải rõ ràng và chỉ dẫn đến một ý nghĩa.

• Input - Một thuật toán phải có 0 hoặc nhiều đầu vào được xác định rõ ràng.

• Output - Một thuật toán phải có 1 hoặc nhiều đầu ra được xác định rõ và phải phù hợp với đầu ra mong muốn.

• Finiteness - Thuật toán phải kết thúc sau một số bước hữu hạn.

• Feasibility - Nên khả thi với các nguồn lực sẵn có.

• Independent - Một thuật toán phải có hướng dẫn từng bước, điều này phải độc lập với bất kỳ mã lập trình nào.

Làm thế nào để viết một thuật toán?

Không có tiêu chuẩn được xác định rõ ràng để viết thuật toán. Đúng hơn, đó là vấn đề và phụ thuộc vào tài nguyên. Các thuật toán không bao giờ được viết để hỗ trợ một mã lập trình cụ thể.

Như chúng ta biết rằng tất cả các ngôn ngữ lập trình đều có chung các cấu trúc mã cơ bản như vòng lặp (do, for, while), điều khiển luồng (if-else), v.v. Những cấu trúc chung này có thể được sử dụng để viết một thuật toán.

Chúng tôi viết các thuật toán theo cách thức từng bước, nhưng không phải lúc nào cũng vậy. Viết thuật toán là một quá trình và được thực hiện sau khi miền vấn đề được xác định rõ. Đó là, chúng ta nên biết miền vấn đề mà chúng ta đang thiết kế một giải pháp.

Thí dụ

Hãy thử tìm hiểu cách viết thuật toán bằng cách sử dụng một ví dụ.

Problem - Thiết kế thuật toán cộng hai số và hiển thị kết quả.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

Các thuật toán cho người lập trình biết cách viết mã chương trình. Ngoài ra, thuật toán có thể được viết dưới dạng:

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

Trong thiết kế và phân tích các thuật toán, thường phương pháp thứ hai được sử dụng để mô tả một thuật toán. Nó giúp nhà phân tích dễ dàng phân tích thuật toán bỏ qua tất cả các định nghĩa không mong muốn. Anh ta có thể quan sát những thao tác nào đang được sử dụng và quy trình đang diễn ra như thế nào.

Viết step numbers, Là tùy chọn.

Chúng tôi thiết kế một thuật toán để có được giải pháp của một vấn đề nhất định. Một vấn đề có thể được giải quyết bằng nhiều cách.

Do đó, nhiều thuật toán giải có thể được rút ra cho một vấn đề nhất định. Bước tiếp theo là phân tích các thuật toán giải pháp được đề xuất đó và triển khai giải pháp phù hợp nhất.

Phân tích thuật toán

Hiệu quả của một thuật toán có thể được phân tích ở hai giai đoạn khác nhau, trước khi thực hiện và sau khi thực hiện. Chúng là những thứ sau -

• A Priori Analysis- Đây là một phân tích lý thuyết của một thuật toán. Hiệu quả của một thuật toán được đo lường bằng cách giả định rằng tất cả các yếu tố khác, ví dụ, tốc độ bộ xử lý, là không đổi và không ảnh hưởng đến việc triển khai.

• A Posterior Analysis- Đây là phân tích thực nghiệm của một thuật toán. Thuật toán đã chọn được thực hiện bằng ngôn ngữ lập trình. Điều này sau đó được thực hiện trên máy tính đích. Trong phân tích này, số liệu thống kê thực tế như thời gian chạy và không gian cần thiết, được thu thập.

Chúng ta sẽ tìm hiểu về phân tích thuật toán tiên nghiệm . Phân tích thuật toán đề cập đến việc thực thi hoặc thời gian chạy của các hoạt động khác nhau có liên quan. Thời gian chạy của một thao tác có thể được định nghĩa là số lượng lệnh máy tính được thực hiện trên mỗi thao tác.

Độ phức tạp của thuật toán

Giả sử X là một thuật toán và n là kích thước của dữ liệu đầu vào, thời gian và không gian mà thuật toán X sử dụng là hai yếu tố chính quyết định hiệu quả của X.

• Time Factor - Thời gian được đo bằng cách đếm số lượng các thao tác chính như so sánh trong thuật toán sắp xếp.

• Space Factor - Không gian được đo bằng cách đếm không gian bộ nhớ lớn nhất mà thuật toán yêu cầu.

Độ phức tạp của một thuật toán f(n) cung cấp thời gian chạy và / hoặc không gian lưu trữ theo yêu cầu của thuật toán về n như kích thước của dữ liệu đầu vào.

Không gian phức tạp

Độ phức tạp không gian của một thuật toán biểu thị lượng không gian bộ nhớ mà thuật toán yêu cầu trong vòng đời của nó. Không gian được yêu cầu bởi một thuật toán bằng tổng của hai thành phần sau:

• Một phần cố định là không gian cần thiết để lưu trữ dữ liệu và biến nhất định, độc lập với quy mô của vấn đề. Ví dụ, các biến và hằng số đơn giản được sử dụng, kích thước chương trình, v.v.

• Một phần biến là một không gian được yêu cầu bởi các biến, kích thước của nó phụ thuộc vào kích thước của bài toán. Ví dụ, cấp phát bộ nhớ động, không gian ngăn xếp đệ quy, v.v.

Độ phức tạp không gian S (P) của bất kỳ thuật toán P nào là S (P) = C + SP (I), trong đó C là phần cố định và S (I) là phần biến của thuật toán, phụ thuộc vào đặc tính cá thể I. Sau đây là một ví dụ đơn giản cố gắng giải thích khái niệm -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Ở đây chúng ta có ba biến A, B, C và một hằng số. Do đó S (P) = 1 + 3. Bây giờ, không gian phụ thuộc vào kiểu dữ liệu của các biến và kiểu hằng đã cho và nó sẽ được nhân lên tương ứng.

Thời gian phức tạp

Độ phức tạp thời gian của một thuật toán biểu thị lượng thời gian mà thuật toán yêu cầu để chạy đến khi hoàn thành. Yêu cầu về thời gian có thể được định nghĩa như một hàm số T (n), trong đó T (n) có thể được đo bằng số bước, miễn là mỗi bước tiêu thụ thời gian không đổi.

Ví dụ, phép cộng hai số nguyên n bit sẽ mất ncác bước. Do đó, tổng thời gian tính toán là T (n) = c ∗ n, trong đó c là thời gian thực hiện phép cộng hai bit. Ở đây, chúng tôi quan sát thấy rằng T (n) tăng tuyến tính khi kích thước đầu vào tăng lên.