我有两种算法可以解决此问题：生成汉明距离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);
}