Độ phức tạp thời gian tiệm cận của việc chèn phần tử n vào đống nhị phân đã chứa các phần tử n

Question

Giả sử chúng ta có một phần tử nhị phân của n phần tử và muốn chèn thêm n phần tử (không nhất thiết phải là một phần tử khác). Tổng thời gian cần thiết cho việc này là bao nhiêu?

Tôi nghĩ rằng đó là theta (n logn) khi chèn một lần.

Answer 1

Giả sử chúng ta đang đưa ra: hàng đợi ưu tiên

• thực hiện theo tiêu chuẩn đống nhị phân H (thực hiện trên mảng)
• n kích thước hiện tại của đống

Chúng tôi đã sau chèn tính:

• W (n) = WorstCase (n) = Θ (lg n) (Theta). -> W (n) = Ω (lg n) và W (n) = O (lg n)
• A (n) = AverageCase (n) = Θ (lg n) (Theta). -> W (n) = Ω (lg n) và W (n) = O (lg n)
• B (n) = BestCase (n) = Θ (1) (Theta). -> W (n) = Ω (1) và W (n) = O (1)

Vì vậy, đối mọi trường hợp, chúng tôi có

• T (n) = Ω (1) và T (n) = O (lg n)

WorstCase là khi, chúng tôi chèn giá trị tối thiểu mới, do đó, heap phải đi toàn bộ chi nhánh.

BestCase là khi, cho tối thiểu-đống (đống với tối thiểu trên đầu trang), chúng tôi chèn BIG (lớn nhất trên cập nhật chi nhánh) giá trị (do đó, lên đống dừng lại ngay lập tức).

Bạn đã được hỏi về hàng loạt các hoạt động n trên đống chứa đã n yếu tố, đó là kích thước sẽ tăng trưởng

from n to 2*n 

gì tiệm là ...

n=Θ(n) 
2*n=Θ(n) 

gì đơn giản hoá các phương trình của chúng tôi. (Chúng tôi không phải lo lắng về tăng trưởng của n, vì tăng trưởng của nó là do yếu tố không đổi).

Vì vậy, chúng tôi có "cho n chèn" hoạt động:

• Xi (n) = X_for_n_insertions (n)
  • Wi (n) = Θ (n lg n)
  • Ái (n) = Θ (n lg n)
  • Bi (n) = Θ (n)
• nó ngụ ý, vì "tất cả các trường hợp":
  • Ti (n) = Ω (n) và Ti (n) = O (n lg n)

T.B. Để hiển thị các ký hiệu Theta Θ, Omega,, bạn cần cài đặt UTF-8/tương thích.

Answer 2

nó không theeta (nlogn) ... trật tự của nó (nlogn) kể từ khi một số các chèn có thể mất ít thời gian sau đó logn chính xác ... Vì thế cho n chèn nó sẽ mất thời gian < = nlogn

= > thời gian phức tạp = O (nlogn)

Answer 3

được cung cấp: có nhiều phần tử n và n phần tử khác được chèn vào. Vì vậy, cuối cùng sẽ có 2 * n yếu tố. vì heap có thể được tạo theo 2 cách 1. Chèn thành công và 2. Xây dựng phương thức heap. Amoung các phương pháp xây dựng heap mất O (n) thời gian để xây dựng đống được giải thích trong How can building a heap be O(n) time complexity?. vì vậy tổng thời gian được yêu cầu là O (2 * n) giống như O (n)