尝试比较递归算法和迭代算法 [英] Trying to compare a recursive and an iterative algorithm

问题描述

我有两种算法可以解决此问题：全部生成汉明距离t 内的比特序列。现在我想从理论上比较它们（如果需要的话，我确实有时间测量）。

I have two algorithms that solve this problem: Generate all sequences of bits within Hamming distance t. Now I want to compare them theoretically (I do have time measurements, if needed).

迭代算法的复杂度为：

O（（n选择t）* n）

O((n choose t) * n)

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

where n is the length of the bit-string and t is the desired Hamming distance.

递归算法，到目前为止，它们最好的是：

The recursive algorithm, they best we have so far is:

O（2 ^ n）

O(2^n)

但是如何比较这两个时间复杂度而不引入 t 在第二个时间复杂度内？因此，我正在尝试这样做，您能帮忙吗？

but how to compare these two Time Complexities, without introducing t inside the second Time Complexity? For that reason, I am trying to do that, can you help?

递归算法：

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

推荐答案

递归算法为 O（（n选择t）* n）也可以通过分析对打印出的每个组合收取打印时整个调用堆栈的成本。我们之所以这样做是因为每次 magic 的调用（除了两个 O（1）叶子调用，其中 i< 0 ，我们可以很容易地删除它）打印一些东西。

The recursive algorithm is O((n choose t) * n) too, by an analysis that charges to each printed combination the cost of the entire call stack at the time that it is printed. We can do this because every invocation of magic (except the two O(1) leaf calls where i < 0, which we could easily do away with) prints something.

如果您指定打印它的边界，则最好真实成本。否则，我很确定可以将这两种分析的结果都拉紧到 O（n选择t），而不必打印 t> 0 ，详细信息在Knuth 4A中。

This bound is best possible if you assign printing its true cost. Otherwise, I'm pretty sure that both analyses can be tightened to O(n choose t) excluding printing for t > 0, with details in Knuth 4A.

这篇关于尝试比较递归算法和迭代算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！