1

除了这段代码效率低下之外，我在这里编写递归函数的方式是否被认为是“好风格”。例如，我正在做的事情是创建一个包装器，然后将它传递给int mid和一个计数器int count。

这段代码所做的是从数组中获取值，然后查看它blockIndex是否大于mid. 那么，除了效率低下，我会得到一份编写这样的递归函数的工作吗？

int NumCriticalVotes :: CountCriticalVotesWrapper(Vector<int> & blocks, int blockIndex)
{

    int indexValue = blocks.get(blockIndex);
    blocks.remove(blockIndex);
    int mid = 9;

    return CountCriticalVotes(blocks, indexValue, mid, 0);
}


int NumCriticalVotes :: CountCriticalVotes(Vector<int> & blocks, int blockIndex, int mid, int counter)
{
    if (blocks.isEmpty())
    {
        return counter;
    }

    if (blockIndex + blocks.get(0) >= mid)
    {
        counter += 1;
    } 

    Vector<int> rest = blocks;
    rest.remove(0);
    return CountCriticalVotes(rest, blockIndex, mid, counter);
}
4

5 回答 5

2

这是有效的，它适用于足够小的集合。

然而，它的效率非常低——对于每个递归调用，您都在创建 Vector 的整个未计算部分的副本。因此，如果您计算一个包含 1000 个项目的向量，您将首先创建一个包含 999 个项目的向量，然后再创建一个包含 998 个项目的向量，然后再创建一个包含 997 个项目的向量，以此类推，一直到 0 个项目。

这本身会非常浪费，但似乎会变得更糟。然后，您正在从 Vector 中删除一个项目 - 但您正在删除第一个项目。假设您的 Vector 类似于std::vector，删除最后一项需要恒定时间，但删除第一项需要线性时间 - 即，要删除第一项，之后的每个项目都“向前”移动到空出的位置。

这意味着您的算法不是采用恒定空间和线性时间，而是在空间和时间上都是二次的。除非涉及的收藏非常少，否则将是相当浪费的。

我不会为每个调用创建一个全新的 Vector，而是将偏移量传递到现有的 Vector 中。这将避免复制和删除项目，因此使其在时间和空间上都是线性的非常简单（这仍然远未达到最佳状态，但至少不如二次方那么糟糕）。

要进一步减少使用的空间，请将数组视为两半。分别计算每一半，然后将结果相加。这会将递归深度减少到对数而不是线性，这通常是相当大的（例如，对于 1000 个项目，它的深度约为 10 而不是大约 1000。对于一百万个项目，深度上升到大约 20 而不是一百万）。

于 2012-12-12T19:05:37.717 回答
1

在不确切知道您要完成什么的情况下，这是一个非常难以回答的问题。我看到递归或一般编码的方式是它是否满足以下三个要求。

  1. 它是否完成了所有需要的功能？
  2. 它是否具有容错性？这意味着当传递无效输入或边缘情况时它不会中断。
  3. 它是否在足够的时间内完成了它的目标？

我认为您担心数字 3，我可以说时间应该适合问题。例如，如果您搜索 2 个巨大的列表，则 O(n^2) 可能是不可接受的。但是，假设您正在搜索 2 个小集合 O(n^2) 可能足够快。

我能说的是尝试在测试用例上对算法的不同实现进行计时。仅仅因为您的解决方案是递归的，并不意味着它总是比“蛮力”实现更快。（这当然视具体情况而定）。

要回答您的问题，就递归而言，此示例看起来不错。但是，你会得到一份编写这样代码的工作吗？我不知道这对其他两个编码要求的满足程度如何？

于 2012-12-12T18:57:54.423 回答
1

您的解决方案的问题是您传递计数。停止传递计数并使用堆栈来跟踪它。另一个问题是我不确定你的第二个条件是什么。

int NumCriticalVotes :: CountCriticalVotesWrapper(Vector<int> & blocks, int blockIndex)
{

    int indexValue = blocks.get(blockIndex);
    blocks.remove(blockIndex);
    int mid = 9;

    return CountCriticalVotes(blocks, indexValue, mid);
}


int NumCriticalVotes :: CountCriticalVotes(Vector<int> & blocks, int blockIndex, int mid)
{
    if (blocks.isEmpty())
    {
        return 0;
    }

    if (/*Not sure what the condition is*/) 
    {
        return 1 + CountCriticalVotes(blocks, blockIndex, mid);
    }

    return CountCriticalVotes(blocks, blockIndex, mid);
}
于 2012-12-12T19:01:39.357 回答
1

很主观的问题。尾递归很好（在我的书中），但我会在每次调用时创建一个新向量来平衡它，这使得线性算法成为二次方。独立于递归，这是一个很大的禁忌，特别是因为它很容易避免。

一些关于代码打算完成的评论也会有所帮助，尽管我认为在上下文中问题会更小。

于 2012-12-12T19:07:06.110 回答
1

在 C++ 中，使用递归遍历任意长度的列表从来都不是一个好习惯。这不仅仅是关于性能。该标准不强制要求尾调用优化，因此如果您不能保证列表的大小有限，则存在堆栈溢出的风险。

当然，递归深度必须是几十万，典型的堆栈大小，但是在设计程序时很难知道它将来必须能够处理什么样的输入。这个问题可能会在很久以后再次困扰你。

于 2012-12-12T19:14:16.210 回答