快速找到正确组合的算法
Algorithm to find the correct combination in a fast manner
假设我有4个列表：工作、工人、机制和机制设备。
- 目前我首先循环遍历作业，我们称之为
jobLoop.
- 在
jobLoop 中循环 workerLoop，检查是否
工作人员有空并且具备完成工作所需的能力。
- 如果 worker 没问题，我将循环
mechanismLoop，检查 worker 是否可以使用该机制以及该机制是否可用。如果没有可用的机制，我会返回 workerLoop，寻找另一个正确的工人。
- 如果机制没问题，我循环
mechEquipmentLoop，检查工人是否可以使用设备以及设备是否可用。如果没有可用的设备，我会返回 mechanismLoop，寻找另一个正确的机制。
- 如果机械设备终于没问题，算法就完成了。如果不是，算法会说项目无法匹配。
这是一个简化版本，在每个步骤中都有许多检查，例如是否允许在完成作业的对象上使用 worker 等。
我正在想一个更有效的方法来做到这一点。目前这个算法的时间复杂度应该大概是O(n^4)吧？我不是在寻找代码，只是在寻找有关如何执行此操作的指导。
恕我直言 - 这个算法是 O(jwm*e) 而不是 O(n^4)。 j = 职位数，w = 工人数，m = 机械数，e = 机械设备数。
如果这些列表不变并且只需要一次答案，那么这是执行的最佳算法。您至少需要访问所有输入一次。
假设这些列表发生变化，并且同一算法需要针对给定作业多次执行，您可以这样做。
将工人列表存储在 BST（或自平衡树状 AVL）中，以工作能力为关键字。假设如果一个工人有多种能力，那么他的数据将包含在所有能力中。树的创建是 O(wlogw)，这里 w 是唯一能力和工人组合的数量，而不是单独的工人数量。删除、添加和搜索将是 O(logw)。这里我们假设能力 - 工人分布是体面的。假设如果所有工人都只有一种能力，这将再次变为 O(w)。
同样适用于机制和设备。这将使每个级别的搜索达到 O(logm) 和 O(loge)。
因此，对于每个作业，分配的最佳情况是 O(logw * logm * loge)，开销为 O(wlogw + mlogm + eloge)。对于所有作业，它将是 (j * logw * logm * loge)。
假设我有4个列表：工作、工人、机制和机制设备。
- 目前我首先循环遍历作业，我们称之为
jobLoop. - 在
jobLoop中循环workerLoop，检查是否 工作人员有空并且具备完成工作所需的能力。 - 如果 worker 没问题，我将循环
mechanismLoop，检查 worker 是否可以使用该机制以及该机制是否可用。如果没有可用的机制，我会返回workerLoop，寻找另一个正确的工人。 - 如果机制没问题，我循环
mechEquipmentLoop，检查工人是否可以使用设备以及设备是否可用。如果没有可用的设备，我会返回mechanismLoop，寻找另一个正确的机制。 - 如果机械设备终于没问题，算法就完成了。如果不是，算法会说项目无法匹配。
这是一个简化版本，在每个步骤中都有许多检查，例如是否允许在完成作业的对象上使用 worker 等。
我正在想一个更有效的方法来做到这一点。目前这个算法的时间复杂度应该大概是O(n^4)吧？我不是在寻找代码，只是在寻找有关如何执行此操作的指导。
恕我直言 - 这个算法是 O(jwm*e) 而不是 O(n^4)。 j = 职位数，w = 工人数，m = 机械数，e = 机械设备数。
如果这些列表不变并且只需要一次答案，那么这是执行的最佳算法。您至少需要访问所有输入一次。
假设这些列表发生变化，并且同一算法需要针对给定作业多次执行，您可以这样做。
将工人列表存储在 BST（或自平衡树状 AVL）中，以工作能力为关键字。假设如果一个工人有多种能力，那么他的数据将包含在所有能力中。树的创建是 O(wlogw)，这里 w 是唯一能力和工人组合的数量，而不是单独的工人数量。删除、添加和搜索将是 O(logw)。这里我们假设能力 - 工人分布是体面的。假设如果所有工人都只有一种能力，这将再次变为 O(w)。
同样适用于机制和设备。这将使每个级别的搜索达到 O(logm) 和 O(loge)。
因此，对于每个作业，分配的最佳情况是 O(logw * logm * loge)，开销为 O(wlogw + mlogm + eloge)。对于所有作业，它将是 (j * logw * logm * loge)。