Phương pháp algorithm là gì
Giải thuật Algorithms (hay còn gọi là thuật toán) là một tập hợp hữu hạn các chỉ thị để được thực thi theo một thứ tự nào đó để thu được kết quả mong muốn. Nói chung thì giải thuật là độc lập với các ngôn ngữ lập trình, tức là một giải thuật có thể được triển khai trong nhiều ngôn ngữ lập trình khác nhau. Show
Xuất phát từ quan điểm của cấu trúc dữ liệu, dưới đây là một số giải thuật quan trọng:
Đặc điểm của giải thuậtKhông phải tất cả các thủ tục có thể được gọi là một giải thuật. Một giải thuật nên có các đặc điểm sau:
Cách viết một giải thuật ?Bạn đừng tìm, bởi vì sẽ không có bất kỳ tiêu chuẩn nào cho trước để viết các giải thuật. Như bạn đã biết, các ngôn ngữ lập trình đều có các vòng lặp (do, for, while) và các lệnh điều khiển luồng (if-else), … Bạn có thể sử dụng những lệnh này để viết một giải thuật. Chúng ta viết các giải thuật theo cách thức là theo từng bước một. Viết giải thuật là một tiến trình và được thực thi sau khi bạn đã định vị rõ ràng vấn đề cần giải quyết. Từ việc định vị vấn đề, chúng ta sẽ thiết kế ra giải pháp để giải quyết vấn đề đó và sau đó là viết giải thuật. Ví dụ viết giải thuậtBạn theo dõi ví dụ minh họa dưới đây để thấy rõ các bước và cách viết một giải thuật. Tất nhiên là ví dụ dưới đây là khá đơn giản vì đây chỉ là ví dụ minh họa mở đầu cho cách viết giải thuật thôi, nên mình nghĩ càng đơn giản sẽ càng tốt. Bài toán: Thiết kế một giải thuật để cộng hai số và hiển thị kết quả. Bước 1: Bắt đầu Bước 2: Khai báo ba số a, b & c Bước 3: Định nghĩa các giá trị của a & b Bước 4: Cộng các giá trị của a & b Bước 5: Lưu trữ kết quả của Bước 4 vào biến c Bước 6: In biến c Bước 7: Kết thúc Các giải thuật nói cho lập trình viên cách để viết code. Ngoài ra, bạn cũng có thể viết một giải thuật cho bài toán trên như sau: Bước 1: Bắt đầu Bước 2: Lấy giá trị của a & b Bước 3: c ← a + b Bước 4: Hiển thị c Bước 5: Kết thúc Trong khi thiết kế và phân tích các giải thuật, thường thì phương thức thứ hai được sử dụng để miêu tả một giải thuật. Cách thứ hai này giúp dễ dàng phân tích giải thuật khi đã bỏ qua các phần định nghĩa không cần thiết. Nhìn vào cách thứ hai này, người ta có thể biết các phép tính nào đang được sử dụng và cách tiến trình thực thi. Tất nhiên, việc viết tên các bước là tùy ý. Chúng ta viết một giải thuật để tìm giải pháp để xử lý một bài toán nào đó. Một bài toán có thể được giải theo nhiều cách khác nhau. Do đó, một bài toán có thể sẽ có nhiều lời giải. Vậy lời giải nào sẽ là thích hợp nhất cho bài toán đó. Mời bạn tiếp tục theo dõi. Phân tích giải thuậtHiệu quả của một giải thuật có thể được phân tích dựa trên 2 góc độ: trước khi triển khai và sau khi triển khai:
Chương này chúng ta sẽ tìm hiểu phân tích lý thuyết. Còn phân tích tiệm cận chúng ta sẽ cùng tìm hiểu ở chương tiếp theo. Độ phức tạp giải thuật (Algorithm Complexity)Về bản chất, độ phức tạp giải thuật là một hàm ước lượng (có thể không chính xác) số phép tính mà giải thuật cần thực hiện (từ đó dễ dàng suy ra thời gian thực hiện của giải thuật) đối với bộ dữ liệu đầu vào (Input) có kích thước n. Trong đó, n có thể là số phần tử của mảng trong trường hợp bài toán sắp xếp hoặc tìm kiếm, hoặc có thể là độ lớn của số trong bài toán kiểm tra số nguyên tố, … Giả sử X là một giải thuật và n là kích cỡ của dữ liệu đầu vào. Thời gian và lượng bộ nhớ được sử dụng bởi giải thuật X là hai nhân tố chính quyết định hiệu quả của giải thuật X:
Độ phức tạp của một giải thuật (một hàm f(n)) cung cấp mối quan hệ giữa thời gian chạy và/hoặc lượng bộ nhớ cần được sử dụng bởi giải thuật. Độ phức tạp bộ nhớ (Space complexity) trong phân tích giải thuậtNhân tố bộ nhớ của một giải thuật biểu diễn lượng bộ nhớ mà một giải thuật cần dùng trong vòng đời của giải thuật. Lượng bộ nhớ (giả sử gọi là S(P)) mà một giải thuật cần sử dụng là tổng của hai thành phần sau:
Từ trên, ta sẽ có Output: Giải thuật: tìm tổng hai số A, B Step 1 - Bắt đầu Step 2 - C ← A + B + 10 Step 3 - Kết thúc Ở đây chúng ta có ba biến A, B và C và một hằng số. Do đó: Bây giờ, lượng bộ nhớ sẽ phụ thuộc vào kiểu dữ liệu của các biến và hằng đã cho và sẽ bằng tích của tổng trên với bộ nhớ cho kiểu dữ liệu tương ứng. Độ phức tạp thời gian (Time Complexity) trong phân tích giải thuậtNhân tố thời gian của một giải thuật biểu diễn lượng thời gian chạy cần thiết từ khi bắt đầu cho đến khi kết thúc một giải thuật. Thời gian yêu cầu có thể được biểu diễn bởi một hàm T(n), trong đó T(n) có thể được đánh giá như là số các bước. Ví dụ, phép cộng hai số nguyên n-bit sẽ có n bước. Do đó, tổng thời gian tính toán sẽ là T(n) = c*n, trong đó c là thời gian để thực hiện phép cộng hai bit. Ở đây, chúng ta xem xét hàm T(n) tăng tuyến tính khi kích cỡ dữ liệu đầu vào tăng lên. Algorithm trong tin học là gì?Algorithm là gì? Theo toán học khoa học máy tính cũng như các chuyên ngành liên quan thì một thuật toán chính là phương pháp hiệu quả để giải quyết một vấn đề. Vấn đề này được thể hiện dưới dạng một chuỗi hữu hạn các hướng dẫn.
Đặc điểm của thuật toán Algorithm là gì?Thuật toán (ALGORITHM) là bộ các quy luật giải quyết vấn đề bằng việc sử dụng công thức toán học. Trong ngành ngân hàng, thuật toán được dùng để định giá tiền vay, lập mô hình tài chính và quản lý tài sản - công nợ, định giá chuyển nhượng, và bảo mật dữ liệu.
Time complexity and Space complexity là gì?Liên quan đến dung lượng bộ nhớ mà thuật toán đòi hỏi, người ta sử dụng một thước đo để đánh giá, gọi là độ phức tạp không gian (Space Complexity) của thuật toán. Còn để đánh giá thời gian chạy của thuật toán, người ta dùng khái niệm độ phức tạp thời gian (Time Complexity).
Algorithmic complexity là gì?Độ phức tạp giải thuật (Algorithm Complexity)
Về bản chất, độ phức tạp giải thuật là một hàm ước lượng (có thể không chính xác) số phép tính mà giải thuật cần thực hiện (từ đó dễ dàng suy ra thời gian thực hiện của giải thuật) đối với bộ dữ liệu đầu vào (Input) có kích thước n.
|