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

本文介绍了尝试比较递归算法和迭代算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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