Thời gian khấu hao không đổi

Question

Điều gì có nghĩa là "Thời gian phân bổ liên tục" khi nói về độ phức tạp thời gian của một thuật toán?

Answer 1

thời gian khấu hao theo giải thích trong thuật ngữ đơn giản:

Nếu bạn thực hiện một chiến dịch nói hàng triệu lần, bạn không thực sự quan tâm đến trường hợp xấu nhất hoặc trường hợp tốt nhất của hoạt động đó - điều bạn quan tâm là tổng thời gian khi bạn lặp lại hoạt động một triệu lần.

Vì vậy, nó không quan trọng nếu hoạt động rất chậm một lần trong một thời gian, miễn là "một lần trong một thời gian" là hiếm đủ cho sự chậm trễ được pha loãng đi. Về cơ bản thời gian khấu hao có nghĩa là "thời gian trung bình được thực hiện cho mỗi hoạt động, nếu bạn thực hiện nhiều thao tác". Thời gian khấu hao không phải là hằng số; bạn có thể có thời gian khấu hao tuyến tính và logarit hoặc bất kỳ thứ gì khác.

Hãy lấy ví dụ về mảng của mảng động mà bạn liên tục thêm các mục mới. Thông thường, thêm một mục sẽ mất thời gian cố định (nghĩa là, O(1)). Nhưng mỗi khi mảng đầy, bạn phân bổ gấp đôi dung lượng, sao chép dữ liệu của bạn vào vùng mới và giải phóng không gian cũ. Giả sử phân bổ và giải phóng chạy trong thời gian không đổi, quá trình mở rộng này mất O(n) thời gian trong đó n là kích thước hiện tại của mảng.

Vì vậy, mỗi khi bạn phóng to, bạn mất khoảng gấp đôi thời gian như lần phóng to cuối cùng. Nhưng bạn cũng đã đợi lâu gấp hai lần trước khi thực hiện nó! Do đó, chi phí của mỗi lần mở rộng có thể được "trải ra" trong số các lần chèn. Điều này có nghĩa là về lâu dài, tổng thời gian thực hiện để thêm m mục vào mảng là O(m) và do đó, thời gian khấu hao (nghĩa là thời gian cho mỗi lần chèn) là O(1).

Answer 2

Điều đó có nghĩa là theo thời gian, trường hợp xấu nhất sẽ mặc định là O (1) hoặc thời gian không đổi. Một ví dụ phổ biến là mảng động. Nếu chúng ta đã cấp phát bộ nhớ cho một mục mới, việc thêm nó sẽ là O (1). Nếu chúng tôi không phân bổ nó, chúng tôi sẽ làm như vậy bằng cách phân bổ, nói, gấp đôi số tiền hiện tại. Chèn cụ thể này sẽ không phải là là O (1), nhưng thay vào đó là thứ khác.

Điều quan trọng là thuật toán đảm bảo rằng sau một chuỗi hoạt động, các hoạt động tốn kém sẽ được khấu hao và do đó hiển thị toàn bộ hoạt động O (1).

Hoặc trong điều kiện nghiêm ngặt hơn,

Có một c liên tục, như vậy mà cho mỗi chuỗi các hoạt động (cũng là một kết thúc với một hoạt động tốn kém) của chiều dài L, thời gian không phải là lớn hơn c * L (Cảm ơn Rafał Dowgird)

Answer 3

Các giải thích ở trên áp dụng cho Phân tích tổng hợp, ý tưởng lấy "trung bình" trên nhiều hoạt động. Tôi không chắc chắn cách thức họ áp dụng cho phương thức Ngân hàng hoặc Phương pháp phân tích Phân bổ theo phương pháp vật lý.

Hiện tại. Tôi không chắc chắn chính xác câu trả lời đúng. Nhưng nó sẽ phải làm với điều kiện nguyên tắc của cả hai nhà vật lý + Phương pháp của ngân hàng:

(Tổng chi phí hoạt động được phân bổ)> = (Tổng chi phí hoạt động thực tế).

Khó khăn chính mà tôi phải đối mặt là cho rằng chi phí hoạt động tiệm cận khác biệt so với chi phí bình thường, tôi không biết cách đánh giá tầm quan trọng của chi phí phân bổ.

Đó là khi ai đó cho tôi một khoản chi phí phân bổ, tôi biết nó không giống như chi phí bình thường-tiệm cận Những kết luận nào tôi rút ra từ chi phí phân bổ sau đó?

Vì chúng tôi có trường hợp một số hoạt động bị quá tải trong khi các hoạt động khác bị tính phí, một giả thuyết có thể là trích dẫn chi phí khấu hao của các hoạt động riêng lẻ sẽ là vô nghĩa.

Ví dụ: Đối với một đống heap, trích dẫn chi phí phân bổ của chỉ giảm-Key là O (1) là vô nghĩa vì chi phí được giảm bởi "công việc thực hiện bởi các hoạt động trước đó trong tăng tiềm năng của đống."

HOẶC

Chúng ta có thể có một giả thuyết cho rằng lý do về khấu hao-chi phí như sau:

1. Tôi biết rằng các hoạt động đắt tiền sẽ đi trước bởi hoạt động LOW-CHI PHÍ NHIỀU.

2. Để phân tích, tôi sẽ thực hiện quá tải một số hoạt động chi phí thấp, ĐẢM NHẬN CHI PHÍ THỬ NGHIỆM CỦA HỌ KHÔNG THAY ĐỔI.

3. Với các hoạt động chi phí thấp tăng lên này, tôi có thể XÁC NHẬN HOẠT ĐỘNG MỞ RỘNG CÓ CHI PHÍ NHƯ THẾ NÀO NHỎ.

4. Vì vậy, tôi đã cải thiện/giảm ASYMPTOTIC-BOUND của chi phí hoạt động n.

Do đó phân tích chi phí phân bổ + giá trị phân bổ chi phí hiện chỉ áp dụng cho các hoạt động tốn kém. Các hoạt động giá rẻ có cùng chi phí được phân bổ theo giá trị tiệm cận như chi phí bình thường.

Answer 4

tôi thấy bên dưới Wikipedia giải thích hữu ích, sau khi lặp lại đọc cho 3 lần:

Nguồn: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

"Dynamic Mảng

khấu hao Phân tích các hoạt động đẩy cho một mảng động

Hãy xem xét một mảng động có kích thước lớn khi nhiều phần tử được thêm vào nó chẳng hạn như một ArrayList trong Java. bắt đầu với một mảng động kích thước 4, sẽ mất nhiều thời gian để đẩy bốn phần tử vào nó. Tuy nhiên, đẩy phần tử thứ năm vào mảng đó sẽ mất nhiều thời gian hơn vì mảng sẽ phải tạo một mảng mới gấp đôi kích thước hiện tại (8), sao chép các phần tử cũ vào mảng mới và sau đó thêm phần tử mới. Ba hoạt động đẩy tiếp theo tương tự sẽ mất thời gian liên tục, và sau đó việc bổ sung tiếp theo sẽ yêu cầu một kích thước khác tăng chậm là .

Nói chung nếu chúng ta xem xét một số tùy ý của push n để một mảng kích thước n, chúng tôi nhận thấy rằng các hoạt động đẩy dành thời gian liên tục trừ cho người cuối cùng mà mất O (n) thời gian để thực hiện các kích thước gấp đôi hoạt động. Kể từ khi có n hoạt động tổng chúng ta có thể mất trung bình điều này và thấy rằng để đẩy các yếu tố vào mảng động mất: O (n/n) = O (1), thời gian liên tục "

Để. sự hiểu biết của tôi như một câu chuyện đơn giản:

Giả sử bạn có rất nhiều tiền Và bạn muốn xếp chồng lên nhau trong một căn phòng Và, bạn có tay và chân dài, miễn là bạn cần ngay bây giờ hoặc Và, bạn phải điền tất cả trong một phòng, vì vậy nó rất dễ dàng để khóa nó.

Vì vậy, bạn đi thẳng đến cuối/góc phòng và bắt đầu xếp chúng. Khi bạn xếp chồng lên nhau, từ từ căn phòng sẽ hết chỗ. Tuy nhiên, khi bạn điền vào nó rất dễ dàng để ngăn xếp chúng. Có tiền, bỏ tiền. Dễ dàng. Đó là O (1). Chúng tôi không cần phải chuyển tiền trước đó.

Khi hết phòng. Chúng ta cần một căn phòng khác, lớn hơn. Ở đây có vấn đề, vì chúng tôi chỉ có thể có 1 phòng nên chúng tôi chỉ có thể có 1 khóa, chúng tôi cần chuyển tất cả số tiền hiện có trong phòng đó vào phòng lớn hơn mới. Vì vậy, hãy chuyển tất cả tiền, từ phòng nhỏ, sang phòng lớn hơn. Tức là, xếp chồng tất cả chúng một lần nữa. Vì vậy, chúng tôi cần phải di chuyển tất cả số tiền trước đó. Vì vậy, nó là O (N). (giả sử N là tổng số tiền của số tiền trước đó)

Nói cách khác, thật dễ dàng cho đến N, chỉ có 1 thao tác, nhưng khi chúng ta cần chuyển sang phòng lớn hơn, chúng tôi đã thực hiện N hoạt động. Vì vậy, nói cách khác, nếu chúng ta trung bình ra, nó là 1 chèn trong bắt đầu, và 1 di chuyển nhiều hơn trong khi di chuyển đến một phòng khác. Tổng số 2 thao tác, một lần chèn, một lần di chuyển.

Giả sử N là lớn như 1 triệu ngay cả trong căn phòng nhỏ, 2 hoạt động so với N (1 triệu) không thực sự là một số tương đương, vì vậy nó được coi là hằng số hoặc O (1).

Giả sử khi chúng tôi thực hiện tất cả những điều trên ở một phòng lớn hơn, và một lần nữa cần phải di chuyển. Nó vẫn như cũ. nói, N2 (nói, 1 tỷ đồng) là số tiền mới đếm tiền trong phòng lớn hơn

Vì vậy, chúng tôi có N2 (trong đó bao gồm N trước kể từ khi chúng tôi di chuyển tất cả từ nhỏ đến phòng lớn hơn)

Chúng tôi vẫn chỉ cần 2 hoạt động, một là chèn vào phòng lớn hơn, sau đó một hoạt động di chuyển để di chuyển đến một căn phòng lớn hơn.

Vì vậy, ngay cả đối với N2 (1 tỷ), nó là 2 hoạt động cho mỗi. đó không là gì nữa. Vì vậy, nó là hằng số, hoặc O (1)

Vì vậy, khi N tăng từ N đến N2, hoặc khác, nó không quan trọng nhiều. Nó vẫn là hằng số, hoặc O (1) hoạt động cần thiết cho mỗi N.

---

Giả sử bạn có N là 1, rất nhỏ, số tiền nhỏ và bạn có một căn phòng rất nhỏ, chỉ vừa với 1 số tiền.

Ngay khi bạn nạp tiền vào phòng, phòng sẽ được lấp đầy.

Khi bạn đến phòng lớn hơn, giả sử nó chỉ có thể chứa thêm một khoản tiền trong đó, tổng cộng 2 số tiền. Điều đó có nghĩa là, tiền trước đó đã chuyển và thêm 1 lần nữa. Và một lần nữa nó được lấp đầy.

Bằng cách này, chữ N tăng chậm, và không đổi O (1), vì chúng ta đang chuyển tiền từ phòng trước, nhưng chỉ có thể vừa thêm 1 tiền nữa.

Sau 100 lần, phòng mới phù hợp với 100 số tiền từ trước và thêm 1 khoản tiền có thể chứa. Đây là O (N), vì O (N + 1) là O (N), có nghĩa là, mức 100 hoặc 101 là giống nhau, cả hai đều là hàng trăm, trái với câu chuyện trước đó, từ hàng triệu đến hàng tỷ .

Vì vậy, đây là cách phân bổ không hiệu quả (hoặc bộ nhớ/RAM) cho tiền của chúng tôi (biến).

---

Vì vậy, một cách tốt được bố trí thêm chỗ, với quyền hạn của 2.

kích thước phòng 1 = phù hợp với 1 số tiền
kích thước phòng 2 = 4 phù hợp với số tiền
phòng thứ 3 size = phù hợp với 8 đếm tiền
kích thước phòng 4 = phù hợp với 16 đếm tiền
kích thước phòng 5 = phù hợp với 32 đếm tiền
kích thước phòng 6 = phù hợp với 64 đếm tiền
phòng 7 size = phù hợp 128 đếm tiền
kích thước phòng 8 = phù hợp 256 đếm tiền
kích thước phòng 9 = phù hợp 512 đếm tiền
kích thước phòng 10 = fits 1024 count tiền
kích thước phòng 11 = phù hợp với 2.048 tội danh tiền
...
kích thước phòng 16 = 65.536 phù hợp với số tiền
...
kích thước phòng 32th = phù hợp 4,294,967,296 đếm tiền
...
kích thước phòng 64 = phù hợp 18.446.744.073.709.551.616 đếm tiền

Tại sao điều này lại tốt hơn? Bởi vì nó có vẻ phát triển chậm trong đầu, và nhanh hơn sau đó, đó là, so với số lượng bộ nhớ trong bộ nhớ RAM của chúng tôi. Điều này là hữu ích bởi vì, trong trường hợp đầu tiên mặc dù nó là tốt, tổng số công việc phải được thực hiện cho mỗi tiền là cố định (2) và không thể so sánh với kích thước phòng (N), phòng mà chúng tôi đã trong ban đầu giai đoạn có thể quá lớn (1 triệu) mà chúng tôi có thể không sử dụng hoàn toàn tùy thuộc vào việc chúng tôi có thể nhận được nhiều tiền để tiết kiệm ở tất cả trong trường hợp đầu tiên.

Tuy nhiên, trong trường hợp cuối cùng, quyền hạn của 2, nó phát triển trong giới hạn RAM của chúng tôi. Và như vậy, tăng quyền hạn của 2, cả hai phân tích Armotized vẫn không đổi và nó là thân thiện cho RAM giới hạn mà chúng tôi có như ngày hôm nay.

Answer 5

Để phát triển một cách suy nghĩ trực quan về nó, hãy xem xét việc chèn các phần tử vào dynamic array (ví dụ: std::vector trong C++).Hãy vẽ một đồ thị, cho thấy sự phụ thuộc của số hoạt động (Y) cần thiết để chèn các yếu tố N trong mảng:

phần dọc của biểu đồ màu đen tương ứng với tái phân bổ bộ nhớ để mở rộng một mảng. Ở đây chúng ta có thể thấy rằng sự phụ thuộc này có thể được biểu diễn gần như là một dòng. Và phương trình đường này là Y=C*N + b (C là hằng số, b = 0 trong trường hợp của chúng tôi). Do đó, chúng tôi có thể nói rằng chúng tôi cần phải chi tiêu trung bình C*N hoạt động để thêm phần tử N vào mảng hoặc C*1 hoạt động để thêm một phần tử (thời gian cố định được phân bổ).