可以在线性时间内解决,在n ^ 2时间内完成

Question

问题是这样的

建议数据结构并编写程序来计算员工(直接或间接)在线性时间内转介的员工数量.例如

  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 

使用二维数组做到这一点,可以在线性时间内完成吗？

请注意,员工显然不会被他直接或间接推荐的人推荐,因此图表中没有周期.只有一名员工可以推荐新员工.而每位员工都可以推荐多名员工.

Answer 1

图方法：首先构造一个有向图（本例中为树），其中每个节点代表一名员工并指向引用他们的员工的节点。这应该需要 O(N^2) 最坏情况（准确地说是 (N^2)/2 检查），其中 N 是员工数量。在构建此图时，您应该跟踪这棵树的叶子（未推荐任何人的员工），然后修剪这些节点（为其推荐数量分配零）并将推荐数量加 1推荐他们的员工。然后对新叶子重复此操作，除了向每个引用节点添加 2 引用数量。整个修剪和计数过程也应该花费 O(N)，并且最终所有节点都包含每个员工进行的推荐数量。

这是假设您的图表中没有循环或奇怪的两个员工引用同一员工的情况（即它实际上是一棵树）。

因此，不，如果问题的输入数据是您所描述的二进制向量，则无法线性完成。如果我们只给出每个节点所雇用员工的姓名，那么 O(N) 是可能的。