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 hướng dẫn sẽ đượ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 ra độ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 -
- Tìm kiếm - Thuật toán để tìm kiếm một mục trong cấu trúc dữ liệu.
- Sắp xếp - Thuật toán để sắp xếp các mục theo một thứ tự nhất định.
- Chèn - Thuật toán để chèn mục trong cấu trúc dữ liệu.
- Cập nhật - Thuật toán để cập nhật một mục hiện có trong cấu trúc dữ liệu.
- Xóa - 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 có thể được gọi là một thuật toán. Một thuật toán nên có các đặc điểm sau -
- Không rõ ràng - Thuật toán phải rõ ràng và không mơ hồ. Mỗi bước của nó (hoặc các giai đoạ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.
- Đầu vào - Một thuật toán nên có 0 hoặc nhiều đầu vào được xác định rõ.
- Đầu ra - Một thuật toán nên 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.
- Tính hữu hạn - Thuật toán phải chấm dứt sau một số bước hữu hạn.
- Tính khả thi - Nên khả thi với các nguồn lực sẵn có.
- Độc lập - Một thuật toán nên có các hướng dẫn từng bước, độ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õ để viết thuật toán. Thay vào đó, nó là vấn đề và phụ thuộc 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 chia sẻ các cấu trúc mã cơ bản như các vòng lặp (do, for, while), điều khiển luồng (if-other), v.v. Những cấu trúc phổ biến 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 từng bước, nhưng không phải lúc nào cũng như 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ử học viết thuật toán bằng cách sử dụng một ví dụ.
Vấn đề - Thiết kế một thuật toán để thêm 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 − STOPCác thuật toán cho các lập trình viên biết cách mã hóa chương trình. Ngoài ra, thuật toán có thể được viết là -
Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOPTrong thiết kế và phân tích các thuật toán, thông 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 hoạt động đang được sử dụng và quá trình đang diễn ra như thế nào.
Viết số bước , là tùy chọn.
Chúng tôi thiết kế một thuật toán để có được một giải pháp cho một vấn đề nhất định. Một vấn đề có thể được giải quyết theo nhiều cách.
Do đó, nhiều thuật toán giải pháp có thể được bắt nguồn 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à thực hiện 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. Họ là những người sau đây -
- Phân tích Priori - Đây là phân tích lý thuyết về thuật toán. Hiệu quả của một thuật toán được đo bằng cách giả sử rằng tất cả các yếu tố khác, ví dụ, tốc độ của bộ xử lý, là không đổi và không ảnh hưởng đến việc thực hiện.
- Phân tích Posterior - Đây là một 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 mục tiêu. 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ề một phân tích thuật toán tiên nghiệm . Phân tích thuật toán liên quan đến việc thực hiện hoặc thời gian chạy của các hoạt động khác nhau liên quan. Thời gian chạy của một hoạt động 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 hoạt động.
Độ phức tạp 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 được sử dụng bởi thuật toán X là hai yếu tố chính, quyết định hiệu quả của X.
- Yếu tố thời gian - 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.
- Yếu tố không gian - Không gian được đo bằng cách đếm không gian bộ nhớ tối đa theo yêu cầu của thuật toán.
Độ phức tạp của thuật toán f (n) cho thời gian chạy và / hoặc không gian lưu trữ được yêu cầu bởi thuật toán theo n là 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 thuật toán biểu thị lượng không gian bộ nhớ theo yêu cầu của thuật toán 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 kích thước của vấn đề. Ví dụ, các biến và hằng đơ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, có kích thước phụ thuộc vào kích thước của vấ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 thể hiện I. 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 và 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 đã cho và các loại hằng và nó sẽ được nhân lên tương ứng.
Độ phức tạp thời gian
Độ phức tạp thời gian của 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 là hàm số T (n), trong đó T (n) có thể được đo là số bước, miễn là mỗi bước tiêu tốn thời gian không đổi.
Ví dụ, việc thêm hai số nguyên n bit có n 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 để thêm hai bit. Ở đây, chúng tôi quan sát thấy T (n) tăng trưởng tuyến tính khi kích thước đầu vào tăng.
Được cập nhật: 15 tháng 4 lúc 8:00:15 | Lượt xem: 644
