c++ - 负相关程序的一个例子

Question

我希望构建 2 个负相关函数，这意味着例如

void program()
{
   f1(x);
   f2(x);
}

f1 和 f2 函数都依赖于输入 x 并且我希望当 f1 的执行时间> 正在增加，f2 应该减少，反之亦然。

我认为参数 x 是随机生成的数组，f1 是排序算法。但是，我想不出 f2 的例子。

谁能给我一个这样的函数对的例子吗？

编辑 1: 实际上我找到了一个 f1 和 f2 的例子来满足我的需要。最初我忘了提到这些函数需要是现实的，这意味着我不是在每个函数中寻找简单的 sleep() 调用。我还写了 x 以表示一些“抽象”输入，它可以是现实中的任何东西。

我分别构建f1和f2如下:

void f1(x)
{
   //sort first x elements of an array
}

void f2(x)
{
   //sort last MAXSIZE - x elements of an array
}

这样如果我在每次试验中随机创建一个数组和一个 x，f1 和 f2 将执行完全负相关并且 f1 和f2 成为现实的程序。下面是f1和f2分别执行时间的相关图。

Answer 1

如果 f1() 是一个 O(nlogn) 排序过程，这将要求 f2() 是一个 O(1/(nlogn)) 过程。随着输入规模的增加，这样的过程会变得更容易。我从未听说过这样的算法(并不是说不存在)。

如果总执行时间有一些自然上限，f2() 可以等待一段时间 = UPPER_BOUND - f1() 执行时间的估计。如果 f1() 对于某个 k 的执行时间为 knlogn，则

void f2(x)
{
sleep (UPPER_BOUND - k * size(x) * log(size(x)));
}

似乎可行。

f1() 和 f2() 不是独立的程序而是一起在某个程序上工作的情况是不同的。这里我想到一个问题，比如AI搜索，既可以正向链接方式进行，也可以反向链接方式进行。

如果 f1() 是尝试通过前向链接到达目标节点 https://en.wikipedia.org/wiki/Forward_chaining f2() 是尝试通过向后链接 https://en.wikipedia.org/wiki/Backward_chaining 在公理集中建立目标节点因此，f1() 和 f2() 一起尝试解决搜索问题，那么人们可能希望 f1() 和 f2() 具有所需的行为。

如果 f1() 和 f2() 并行运行，那么很可能如果问题对 f1() 来说很容易，那么对 f2() 来说就很难了，反之亦然，因为搜索难度不会对称。

这类似于双向搜索问题。事实上，经过深思熟虑，这是一个比乍看之下更有问题的问题，因为它可以深入了解一整类双向搜索问题的行为。

双向搜索的动机是 f1() 和 f2() 会以某种方式“在中间相遇”(参见 Bratko https://slideplayer.com/slide/3351420/)，这意味着它们之间的通信

在你描述的情况下，我会争辩说 f1() 和 f2() 不能同时交流，但它们是不同的程序，但是如果一个方向的分支因子与另一个方向非常不同但你寻求的现象就会出现一开始不知道最便宜的方向。