DAA - Phương pháp phân tích
Để đo lường mức tiêu thụ tài nguyên của một thuật toán, các chiến lược khác nhau được sử dụng như đã thảo luận trong chương này.
Phân tích tiệm cận
Hành vi tiệm cận của một hàm f(n) đề cập đến sự phát triển của f(n) như n trở nên lớn.
Chúng tôi thường bỏ qua các giá trị nhỏ của n, vì chúng tôi thường quan tâm đến việc ước tính xem chương trình sẽ chậm như thế nào trên các đầu vào lớn.
Một nguyên tắc chung là tốc độ phát triển tiệm cận càng chậm thì thuật toán càng tốt. Mặc dù nó không phải lúc nào cũng đúng.
Ví dụ, một thuật toán tuyến tính $ f (n) = d * n + k $ luôn tiệm cận tốt hơn một thuật toán bậc hai, $ f (n) = cn ^ 2 + q $.
Giải phương trình lặp lại
Sự tái diễn là một phương trình hoặc bất đẳng thức mô tả một hàm theo giá trị của nó trên các đầu vào nhỏ hơn. Các lần lặp lại thường được sử dụng trong mô hình chia để trị.
Hãy để chúng tôi xem xét T(n) là thời gian chạy về vấn đề kích thước n.
Nếu kích thước sự cố đủ nhỏ, hãy nói n < c Ở đâu c là một hằng số, giải pháp đơn giản cần thời gian không đổi, được viết là θ(1). Nếu phép chia của bài toán tạo ra một số bài toán con có kích thước $ \ frac {n} {b} $.
Để giải quyết vấn đề, thời gian cần thiết là a.T(n/b). Nếu chúng ta coi thời gian cần thiết để phân chia làD(n) và thời gian cần thiết để kết hợp các kết quả của các bài toán con là C(n), quan hệ lặp lại có thể được biểu diễn dưới dạng:
$$ T (n) = \ begin {case} \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \ theta (1) & if \: n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) & nếu không thì \ end { trường hợp} $$
Quan hệ lặp lại có thể được giải quyết bằng cách sử dụng các phương pháp sau:
Substitution Method - Trong phương pháp này, chúng tôi đoán một giới hạn và sử dụng quy nạp toán học, chúng tôi chứng minh rằng giả định của chúng tôi là đúng.
Recursion Tree Method - Trong phương pháp này, một cây lặp lại được hình thành trong đó mỗi nút đại diện cho chi phí.
Master’s Theorem - Đây là một kỹ thuật quan trọng khác để tìm độ phức tạp của quan hệ lặp lại.
Phân tích khấu hao
Phân tích khấu hao thường được sử dụng cho các thuật toán nhất định trong đó một chuỗi các hoạt động tương tự được thực hiện.
Phân tích khấu hao đưa ra ràng buộc về chi phí thực tế của toàn bộ chuỗi, thay vì ràng buộc chi phí của chuỗi hoạt động riêng lẻ.
Phân tích khấu hao khác với phân tích trường hợp trung bình; xác suất không liên quan đến phân tích khấu hao. Phân tích khấu hao đảm bảo hiệu suất trung bình của từng hoạt động trong trường hợp xấu nhất.
Nó không chỉ là một công cụ để phân tích, mà còn là một cách suy nghĩ về thiết kế, vì thiết kế và phân tích có liên quan chặt chẽ với nhau.
Phương pháp tổng hợp
Phương pháp tổng hợp đưa ra cái nhìn toàn cục về một vấn đề. Trong phương pháp này, nếun hoạt động mất thời gian trong trường hợp xấu nhất T(n)Tổng cộng. Khi đó, chi phí phân bổ của mỗi hoạt động làT(n)/n. Mặc dù các hoạt động khác nhau có thể mất thời gian khác nhau, trong phương pháp này, chi phí khác nhau được bỏ qua.
Phương pháp kế toán
Trong phương pháp này, các khoản phí khác nhau được ấn định cho các nghiệp vụ khác nhau theo chi phí thực tế của chúng. Nếu chi phí phân bổ của một hoạt động vượt quá chi phí thực tế của nó, thì phần chênh lệch đó được gán cho đối tượng như một khoản ghi có. Khoản tín dụng này giúp thanh toán cho các hoạt động sau này mà chi phí phân bổ nhỏ hơn chi phí thực tế.
Nếu chi phí thực tế và chi phí phân bổ của ith hoạt động là $ c_ {i} $ và $ \ hat {c_ {l}} $, sau đó
$$ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ hat {c_ {l}} \ geqslant \ displaystyle \ sum \ limit_ {i = 1} ^ n c_ {i} $$
Phương pháp tiềm năng
Phương pháp này thể hiện công việc trả trước là năng lượng tiềm năng, thay vì coi công việc trả trước là tín dụng. Năng lượng này có thể được giải phóng để chi trả cho các hoạt động sau này.
Nếu chúng tôi thực hiện n hoạt động bắt đầu với cấu trúc dữ liệu ban đầu D0. Hãy để chúng tôi xem xét,ci như chi phí thực tế và Di như cấu trúc dữ liệu của ithhoạt động. Hàm tiềm năng Ф ánh xạ tới một số thực Ф (Di), tiềm năng liên quan của Di. Chi phí phân bổ $ \ hat {c_ {l}} $ có thể được xác định bởi
$$ \ hat {c_ {l}} = c_ {i} + \ Phi (D_ {i}) - \ Phi (D_ {i-1}) $$
Do đó, tổng chi phí khấu hao là
$$ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ hat {c_ {l}} = \ displaystyle \ sum \ limit_ {i = 1} ^ n (c_ {i} + \ Phi (D_ {i} ) - \ Phi (D_ {i-1})) = \ displaystyle \ sum \ limit_ {i = 1} ^ n c_ {i} + \ Phi (D_ {n}) - \ Phi (D_ {0}) $ $
Bảng động
Nếu không gian được phân bổ cho bảng không đủ, chúng ta phải sao chép bảng vào bảng kích thước lớn hơn. Tương tự, nếu số lượng lớn thành viên bị xóa khỏi bảng, bạn nên phân bổ lại bảng với kích thước nhỏ hơn.
Sử dụng phân tích khấu hao, chúng ta có thể chỉ ra rằng chi phí khấu hao của việc chèn và xóa là không đổi và không gian chưa sử dụng trong bảng động không bao giờ vượt quá một phần không đổi của tổng không gian.
Trong chương tiếp theo của hướng dẫn này, chúng ta sẽ thảo luận ngắn gọn về Ký hiệu tiệm cận.