nó có thể được giải quyết trong thời gian tuyến tính, đã làm điều này trong n^2 lần

Question

vấn đề đi như thế này

đề nghị một cấu trúc dữ liệu và viết một chương trình để đếm số lượng nhân viên giới thiệu bởi một nhân viên (trực tiếp hoặc gián tiếp) trong thời gian tuyến tính. ví dụ:

A B C D E F G 
A 0 1 0 0 0 0 0 A referred 4 (A referred B, B referred C and D and D referred E) 
B 0 0 1 1 0 0 0 B referred 3 
C 0 0 0 0 0 0 0 
D 0 0 0 0 1 0 0 D referred 1 
E 0 0 0 0 0 0 0 
F 0 0 0 0 0 0 1 F referred 1 
G 0 0 0 0 0 0 0 

thực hiện việc này bằng mảng hai chiều, có thể thực hiện trong thời gian tuyến tính không?

Lưu ý rằng một nhân viên rõ ràng có thể không được đề xuất bởi một người nào đó mà anh ta đề xuất trực tiếp hoặc gián tiếp, vì vậy sẽ không có chu kỳ trong biểu đồ. Một nhân viên mới có thể được đề nghị bởi chỉ một nhân viên. trong khi mỗi nhân viên có thể giới thiệu nhiều nhân viên.

Answer 1

Phương thức biểu đồ: đầu tiên xây dựng biểu đồ được chỉ dẫn (một cây trong trường hợp này) trong đó mỗi nút đại diện cho một nhân viên và trỏ tới nút của nhân viên đã giới thiệu họ. Điều này sẽ có trường hợp xấu nhất O (N^2) ((N^2)/2 kiểm tra chính xác) trong đó N là số lượng nhân viên. Bạn nên, khi bạn đang xây dựng biểu đồ này, theo dõi các lá của cây này (các nhân viên không tham khảo bất kỳ ai) và sau đó cắt các nút này (gán số không cho số lượng giới thiệu của chúng) và thêm 1 vào số lượng các giới thiệu của các nhân viên đã giới thiệu họ. Sau đó lặp lại với các lá mới, ngoại trừ thêm 2 cho mỗi nút giới thiệu của họ số lượng giới thiệu. Toàn bộ quá trình cắt và đếm này cũng cần có O (N), và ở cuối tất cả các nút chứa số lượng các giới thiệu mà mỗi nhân viên thực hiện.

Điều này giả định không có chu kỳ hoặc hai nhân viên kỳ lạ-giới thiệu-cùng-nhân viên tình huống trong biểu đồ của bạn (tức là trên thực tế là một cây).

Vì vậy, không, không thể thực hiện tuyến tính nếu dữ liệu đầu vào cho vấn đề là các vectơ nhị phân bạn đã mô tả. Nếu chúng ta được chỉ đơn giản là tên của các nhân viên được thuê với mỗi nút, thì O (N) sẽ là có thể.

Answer 2

Giải pháp của tôi khi sử dụng C#, tôi chắc chắn điều này nhỏ hơn N^2 nhưng tôi sẽ cần phải xem xét nó lâu hơn một chút. Đăng bài phê bình trong khi tôi làm như vậy.

public class Employee 
{ 
    public List<Employee> Referred { get; set; } 
    public string Name { get; set; } 
    public int CountOfRefer { get; set; } 
    public bool BeenCounted { get; set; } 
    public Employee() 
    { 
     Referred = new List<Employee>(); 
    } 
} 

    public static void main() 
    { 
     Employee A = new Employee(){ Name="A" }; 
     Employee B = new Employee(){ Name="B" }; 
     Employee C = new Employee(){ Name="C" }; 
     Employee D = new Employee(){ Name="D" }; 
     Employee E = new Employee(){ Name="E" }; 
     Employee F = new Employee(){ Name="F" }; 
     Employee G = new Employee(){ Name="G" }; 

     A.Referred.Add(B); 
     B.Referred.Add(C); 
     B.Referred.Add(D); 
     D.Referred.Add(E); 
     F.Referred.Add(G); 
     List<Employee> employees = new List<Employee>() 
     { 
      A, B, C, D, E, F, G 
     }; 

     foreach (var emp in employees) 
     { 
      if (!emp.BeenCounted) countRefers(emp); 
     } 
    } 

    private static int countRefers(Employee emp) 
    { 
     if (!emp.BeenCounted && emp.Referred.Count != 0) 
     { 
      foreach (var refs in emp.Referred) 
      { 
       emp.CountOfRefer += countRefers(refs); 
      } 
     } 

     emp.BeenCounted = true; 
     emp.CountOfRefer += emp.Referred.Count; 
     return emp.CountOfRefer; 
    } 

Về cơ bản khi đếm một nhân viên nó recurses xuống cây cho đến khi nó tìm thấy một người không có liên quan (mà phải được đảm bảo để có mặt ở đó, vì mọi người không thể tham khảo eachother (tôi đoán trừ khi có chỉ là 1 người, bỏ qua trường hợp đó bây giờ)). Sau đó, nếu nó có để tính toán bất cứ ai thông qua đệ quy nó đặt một lá cờ để nó không cần phải tính toán nó một lần nữa.

Answer 3

Bạn có thể tạo biểu đồ trước. Này không được bao gồm trong O (n) vì nó rõ ràng là O (n^2)

Nó không phải là rõ ràng nếu bạn tối ưu hóa các tài liệu tham khảo trùng lặp (Hãy tưởng tượng tất cả các giá trị là 1)

Tại đây bạn có thể bắt đầu tại một nút và thêm tất cả các nút được gọi trong một mặt nạ bit. Bất kỳ giá trị nào đã được thêm vào, bạn cần điều hướng đệ quy cho đến khi bạn không thêm nút mới nào.

Số lượng nút bạn truy cập là O (N) vì mỗi nhân viên có thể giới thiệu một người.

Answer 4

Java Nếu gian lận được cho phép: enum có thể đại diện cho biểu đồ. Viết đầu tiên A (B), B (C, D), ... và sau đó sắp xếp lại để không có tham chiếu về phía trước mà trình biên dịch phàn nàn. (Điều này luôn có thể cho các tham chiếu không tuần hoàn. Ngay cả kiểm tra thời gian biên dịch đối với các tham chiếu tuần hoàn.)

public class Refers { 
    enum RefEnum { 
     C(), 
     E(), 
     G(), 
     D(E), 
     F(G), 
     B(C, D), 
     A(B); 

     //private final RefEnum[] refs; 
     public final int refCount; 

     private RefEnum(final RefEnum... refs) { 
      //this.refs = refs; 
      int n = 0; 
      for (RefEnum ref : refs) { 
       n += 1 + ref.refCount; 
      } 
      refCount = n; 
     } 
    } 

    public static void main(String[] args) { 
     for (RefEnum ref : RefEnum.values()) { 
      System.out.printf("%s has %d refers%n", 
        ref.toString(), ref.refCount); 
     } 
    } 
} 

Thuật toán vẫn là O (N²).

Answer 5

Đây là một cái cây (chính xác hơn là một khu rừng). Đọc các cạnh trong thời gian O (n). Xây dựng cây trong O (n.log (n)). Cho một nút, truy cập và đếm con cháu trong O (n).

Answer 6

Bạn có thể duy trì danh sách kề cho tất cả nhân viên (không gian N). Sau đó cho mỗi nhân viên, duy trì một túi như cấu trúc dữ liệu cho tất cả các nhân viên được giới thiệu. Sau đó, để đếm các tham chiếu cho Employee A, bạn có thể chạy DFS (Depth First Search) bắt đầu từ A là thuật toán thời gian tuyến tính.

mã Java là ở đây -

http://yogeshsp.blogspot.com/2013/04/graph-api.html

http://yogeshsp.blogspot.com/2013/05/depth-first-search-dfs-graph-processing.html