Có một thuật toán O (n) để xây dựng một vùng tối đa không?

Question

Với một dãy số, có một thuật toán O (n) để tạo một vùng tối đa không?

Answer 1

Tôi không nghĩ vậy. Tôi nghĩ rằng tốt nhất bạn có thể làm là O (log n) hoặc tốt hơn một chút với một cái gì đó giống như một đống heap.

Answer 2

Gợi ý: Giả sử thay vì mảng, bạn được cung cấp một cây nhị phân tùy ý. Bạn có thể nghĩ ra một cách hiệu quả để sửa bất kỳ nút nào không thỏa mãn thuộc tính heap không?

Answer 3

Nếu bạn sử dụng Fibonacci Heap bạn nhận được amortized O (1) chèn. Bạn có thể xây dựng một heap tối đa trong phân bổ O (n) từ một mảng.

Việc triển khai như vậy, tôi để lại dưới dạng bài tập *.

_{* Mặc dù, có các triển khai mẫu được liên kết trên trang Wikipedia.}

Answer 4

Có đó là: Building a heap.

Answer 5

Vâng, giống như trong mã này:

for (int i = N/2; i >= 0; --i) 
    push_heap(heap + i, N - i); 

(push_heap là một chức năng chấp nhận một con trỏ đến một đống và kích thước heap và đẩy phía trên cùng của đống cho đến khi các điều kiện đống được tôn trọng hoặc nút đạt đến đáy của đống).

Để có được tại sao điều này là O (N) nhìn vào cây nhị phân hoàn chỉnh:

• 1/2 yếu tố (mức cuối cùng, i> N/2) được đẩy xuống tối đa là 0 bước -> N/2 * 0 hoạt động
• 1/4 phần tử (cấp 1, i> N/4) được đẩy xuống tối đa 1 bước -> N/4 * 1 hoạt động

• 1/8 phần tử (cuối cùng- 2 cấp độ, i> N/8) được đẩy xuống tối đa 2 bước -> N/8 * 2 hoạt động ...

  N/4 * 1 + N/8 * 2 + N/16 * 3 + ... = 
  
      N/4 * 1 + N/8 * 1 + N/16 * 1 + ... + 
        N/8 * 1 + N/16 * 2 + ... = 
  
      N/4 * 1 + N/8 * 1 + N/16 * 1 + ... + // < N/2 
        N/8 * 1 + N/16 * 1 + ... + // < N/4 
           N/16 * 1 + ... + // < N/8 
             ... = // N/2 + N/4 + N/8 + ... < N 
  

Hy vọng rằng toán học không thực sự quá phức tạp. Nếu bạn nhìn vào cây và thêm bao nhiêu mỗi nút có thể được đẩy xuống, bạn sẽ thấy giới hạn trên O (N).