c++ - 尝试比较递归和迭代算法

Question

我有两个算法可以解决这个问题:Generate all sequences of bits within Hamming distance t .现在我想从理论上比较它们(如果需要，我确实有时间测量)。

iterative algorithm复杂度为:

O((n choose t) * n)

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

recursive algorithm , 到目前为止我们最好的是:

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);
}

Answer 1

递归算法是O((n choose t) * n)同样，通过对每个打印组合收取打印时整个调用堆栈的成本的分析。我们可以这样做是因为每次调用 magic (除了两个 O(1) 叶调用，其中 i < 0 ，我们可以很容易地取消)打印一些东西。

如果您将打印分配给它的真实成本，那么这个界限是最好的。否则，我很确定这两种分析都可以收紧到 O(n choose t)不包括 t > 0 的打印, 在 Knuth 4A 中有详细信息。