Sự khác biệt giữa trường hợp trung bình và phân tích phân bổ

Question

Tôi đang đọc một bài viết về phân tích phân bổ các thuật toán. Sau đây là một đoạn văn bản.

Phân tích phân bổ tương tự như phân tích trường hợp trung bình ở chỗ là liên quan đến chi phí trung bình trên một chuỗi hoạt động. Tuy nhiên, phân tích trường hợp trung bình dựa trên các giả định xác suất về cấu trúc dữ liệu và các phép toán để tính toán thời gian chạy dự kiến ​​của một thuật toán là . Do đó, khả năng ứng dụng của nó là phụ thuộc vào các giả định nhất định về phân bố xác suất của các đầu vào thuật toán .

Một trường hợp trung bình ràng buộc không loại trừ khả năng rằng ai sẽ nhận được “may mắn” và gặp phải một đầu vào mà đòi hỏi nhiều hơn dự kiến ​​ thời gian ngay cả khi các giả định để phân phối xác suất đầu vào là hợp lệ.

Câu hỏi của tôi về đoạn văn bản trên là:

1. Trong đoạn đầu tiên, làm thế nào để phân tích trung bình hợp cụ thể “dựa trên các giả định xác suất về cấu trúc dữ liệu và các hoạt động?” Tôi biết phân tích trung bình hợp cụ thể phụ thuộc vào xác suất đầu vào, nhưng câu lệnh trên nghĩa là gì?

2. Tác giả có ý nghĩa gì trong đoạn thứ hai mà trường hợp trung bình không hợp lệ ngay cả khi phân phối đầu vào hợp lệ?

Cảm ơn!

Answer 1

1. Để có được thời gian phức tạp trung bình hợp cụ thể, bạn cần phải thực hiện các giả định về những gì các "trường hợp trung bình" là. Nếu đầu vào là chuỗi, thì "chuỗi trung bình" là gì? Chỉ có chiều dài quan trọng? Nếu vậy, độ dài trung bình của chuỗi tôi sẽ nhận được là bao nhiêu? Nếu không, các ký tự trung bình trong các chuỗi này là gì? Sẽ khó trả lời những câu hỏi này một cách dứt khoát nếu các chuỗi là, ví dụ, họ. Họ trung bình là gì?

2. Trong hầu hết các mẫu thống kê thú vị, giá trị lớn nhất lớn hơn giá trị trung bình. Điều này có nghĩa là phân tích trường hợp trung bình của bạn đôi khi sẽ đánh giá thấp thời gian/tài nguyên cần thiết cho một số yếu tố đầu vào (có vấn đề). Nếu bạn nghĩ về nó, đối với một PDF đối xứng, phân tích trường hợp trung bình nên đánh giá thấp nhiều như nó đánh giá quá cao. Phân tích trường hợp xấu nhất, OTOH, chỉ xem xét trường hợp có vấn đề nhất (s), và do đó được đảm bảo đánh giá quá cao.

Answer 2

1. Xem xét tính toán mức tối thiểu trong mảng chưa phân loại. Có thể bạn biết rằng nó có thời gian chạy là O(n) nhưng nếu chúng tôi muốn chính xác hơn thì nó sẽ so sánh trong trường hợp trung bình là n/2. Tại sao lại thê nay? bởi vì chúng tôi đang làm một giả định về dữ liệu; chúng tôi giả định rằng mức tối thiểu có thể ở mọi vị trí có cùng xác suất. nếu chúng ta thay đổi giả định này, và chúng ta nói ví dụ rằng xác suất ở vị trí i là ví dụ tăng với i, chúng ta có thể chứng minh một số so sánh khác nhau, ngay cả một ràng buộc tiệm cận khác nhau.

2. Trong đoạn thứ hai, tác giả nói rằng với phân tích trường hợp trung bình, chúng tôi có thể rất không may mắn và có trường hợp trung bình đo được lớn hơn trường hợp điều trị; nhớ lại ví dụ trước, nếu chúng ta không may mắn về các mảng khác nhau có kích thước n và tối thiểu là mỗi lần ở vị trí cuối cùng, chúng tôi sẽ đo một trường hợp trung bình n và không phải là n/2. Điều này không thể xảy ra khi một ràng buộc phân bổ được chứng minh.

Answer 3

Phân tích trường hợp trung bình đưa ra giả định về đầu vào có thể không được đáp ứng trong một số trường hợp nhất định. Vì vậy, nếu đầu vào của bạn không phải là ngẫu nhiên, trong trường hợp xấu nhất hiệu suất thực tế của một thuật toán có thể chậm hơn nhiều so với trường hợp trung bình.

Phân tích phân bổ không đưa ra các giả định như vậy, nhưng nó xem xét tổng hiệu suất của một chuỗi các phép toán thay vì chỉ một thao tác.

Chèn mảng động cung cấp ví dụ đơn giản về phân tích phân bổ. Một thuật toán là phân bổ một mảng kích thước cố định, và khi các phần tử mới được chèn vào, hãy phân bổ một mảng kích thước cố định gấp đôi độ dài cũ khi cần thiết. Trong trường hợp xấu nhất, việc chèn có thể yêu cầu thời gian tỷ lệ thuận với độ dài của toàn bộ danh sách, vì vậy trong trường hợp xấu nhất chèn là một hoạt động O (n). Tuy nhiên, bạn có thể đảm bảo rằng trường hợp xấu nhất như vậy là không thường xuyên, do đó, chèn là một hoạt động O (1) sử dụng phân tích phân bổ. Phân tích phân bổ bất kể đầu vào là gì.