小编典典

尝试比较递归算法和迭代算法

algorithm

我有两种算法可以解决此问题:生成汉明距离t内的所有位序列。现在我要从理论上比较它们(如果需要的话,我确实有时间测量)。

该迭代算法具有的复杂性:

O((n选择t)* n)

其中n,位串的长度t是所需的汉明距离。

到目前为止,我们最好的递归算法是:

O(2 ^ n)

但是如何在不引入t第二个时间复杂度的情况下比较这两个时间复杂度呢?因此,我正在尝试这样做,您能帮忙吗?

递归算法:

// str is the bitstring, i the current length, and changesLeft the
// desired Hamming distance (see linked question for more)
void magic(char* str, int i, int changesLeft) {
        if (changesLeft == 0) {
                // assume that this is constant
                printf("%s\n", str);
                return;
        }
        if (i < 0) return;
        // flip current bit
        str[i] = str[i] == '0' ? '1' : '0';
        magic(str, i-1, changesLeft-1);
        // or don't flip it (flip it again to undo)
        str[i] = str[i] == '0' ? '1' : '0';
        magic(str, i-1, changesLeft);
}

阅读 350

收藏
2020-07-28

共1个答案

小编典典

递归算法也是O((n choose t)*n)一种分析,它对每个打印的组合收取打印时整个调用堆栈的成本。我们之所以这样做,是因为每次调用magic(除了两个O(1)叶子调用where i< 0,我们可以很容易地取消它们)都会打印出一些内容。

如果您指定打印其真实成本,则此边界最好。否则,我非常确定可以将这两种分析的结果严格化,以O(n choose t)排除t > 0使用Knuth4A中的详细信息进行打印。

2020-07-28