迭代算法的时间复杂度

Question

迭代算法的时间复杂度

c++algorithmloopsbit-manipulationtime-complexity

3

我正在尝试找到此算法的时间复杂度。

这个迭代的算法会生成给定汉明距离内的所有位字符串，从输入位串开始。它生成所有递增序列0 <= a [0] <...< a [dist-1] < strlen（num），并反转相应索引处的位。

向量a应该保留需要反转比特的索引。所以如果a包含当前索引i，我们打印1而不是0，反之亦然。否则，我们按原样打印位（请参见else部分），如下所示：

// e.g. hamming("0000", 2);
void hamming(const char* num, size_t dist) {
    assert(dist > 0);
    vector<int> a(dist);
    size_t k = 0, n = strlen(num);
    a[k] = -1;
    while (true)
        if (++a[k] >= n)
            if (k == 0)
                return;
            else {
                --k;
                continue;
            }
        else
            if (k == dist - 1) {
                // this is an O(n) operation and will be called
                // (n choose dist) times, in total.
                print(num, a);
            }
            else {
                a[k+1] = a[k];
                ++k;
            }
}

这个算法的时间复杂度是多少？

我的尝试是：

dist * n + (n choose t) * n + 2

但这似乎不正确，考虑以下例子，其中所有距离都为2：

len = 3, (3 choose 2) = 3 * O(n), 10 while iterations
len = 4, (4 choose 2) = 6 * O(n), 15 while iterations
len = 5, (5 choose 2) = 9 * O(n), 21 while iterations
len = 6, (6 choose 2) = 15 * O(n), 28 while iterations

以下是两个代表性的运行示例（在循环开始时进行打印）：

000, len = 3
k = 0, total_iter = 1
vector a = -1 0 
k = 1, total_iter = 2
vector a = 0 0 
Paid O(n)
k = 1, total_iter = 3
vector a = 0 1 
Paid O(n)
k = 1, total_iter = 4
vector a = 0 2 
k = 0, total_iter = 5
vector a = 0 3 
k = 1, total_iter = 6
vector a = 1 1 
Paid O(n)
k = 1, total_iter = 7
vector a = 1 2 
k = 0, total_iter = 8
vector a = 1 3 
k = 1, total_iter = 9
vector a = 2 2 
k = 0, total_iter = 10
vector a = 2 3 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gsamaras@pythagoras:~/Desktop/generate_bitStrings_HammDistanceT$ ./iter
0000, len = 4
k = 0, total_iter = 1
vector a = -1 0 
k = 1, total_iter = 2
vector a = 0 0 
Paid O(n)
k = 1, total_iter = 3
vector a = 0 1 
Paid O(n)
k = 1, total_iter = 4
vector a = 0 2 
Paid O(n)
k = 1, total_iter = 5
vector a = 0 3 
k = 0, total_iter = 6
vector a = 0 4 
k = 1, total_iter = 7
vector a = 1 1 
Paid O(n)
k = 1, total_iter = 8
vector a = 1 2 
Paid O(n)
k = 1, total_iter = 9
vector a = 1 3 
k = 0, total_iter = 10
vector a = 1 4 
k = 1, total_iter = 11
vector a = 2 2 
Paid O(n)
k = 1, total_iter = 12
vector a = 2 3 
k = 0, total_iter = 13
vector a = 2 4 
k = 1, total_iter = 14
vector a = 3 3 
k = 0, total_iter = 15
vector a = 3 4

- gsamaras

2个回答

1

请注意，给定表示长度的n和表示所需距离的t，在1和n（或索引形式下的0和n-1）之间的递增非负序列的数量确实是n choose t，因为我们选择了t个不同的索引。

问题出现在您生成这些序列时：

-首先，请注意，在长度为4的情况下，实际上您会遍历5个不同的索引，从0到4。

-其次，请注意，您正在考虑具有相同索引的序列（在t=2的情况下，它是0 0, 1 1, 2 2等），通常，您将遍历每个非递减序列，而不是每个递增序列。

因此，在计算程序的TC时，请确保考虑到这一点。

提示：尝试从这些序列的宇宙中，建立与某个方程的整数解的宇宙之间的一一对应关系。

如果您需要直接的解决方案，请看这里: https://math.stackexchange.com/questions/432496/number-of-non-decreasing-sequences-of-length-m

最终解决方案是 (n+t-1) 选 (t)，但请注意第一个要点，在您的程序中，实际上应该是 ((n+1)+t-1) 选 (t)，因为您使用了一个额外的索引循环。记作： ((n+1)+t-1) 选 (t) =: A，n 选 t =: B 总体而言，我们得到 O(1) + B*O(n) + (A-B)*O(1)。

- Eliran Abdoo

我认为你的“其次”段落是不正确的。请注意，while循环从无条件递增a[k]开始。（由于某种原因，这已经被混淆到了一个if测试中；但它确实存在。） - ruakh

@ruakh，看了他的运行示例后，我认为它确实会遍历每个非递减序列。我错了吗？ - Eliran Abdoo

他/她的运行示例显示了每个循环迭代开始时向量的内容；但是在循环迭代期间向量被修改了。但是，这很复杂。向量的内容永远不可能像1 1 1（重复三次相同的值）一样，但它们可以暂时像1 1 4或1 2 2这样。 - ruakh

所以，总的来说，你也同意我拥有的算法比Paul提供的算法慢，谢谢，+1。 - gsamaras

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Hankin · Accepted Answer

这个 while 循环有些巧妙而微妙，可以说它正在做两件不同的事情（如果你计算初始化 a 的话，甚至是三件）。这就是使得复杂度计算变得具有挑战性的原因，而且也不够高效。

抽象地说，为了从当前索引逐步计算出下一组索引，想法是找到最后一个小于 n-dist+i 的索引 i，将其增加，并将以下索引设置为 a[i]+1、a[i]+2 等。

例如，如果 dist=5，n=11，而您的索引是：

0, 3, 5, 9, 10

然后找到最后一个小于n-dist+i的值为5（因为n-dist是6，10=6+4，9=6+3，但是5<6+2）。

因此，我们将5增加，并设置随后的整数以获取索引集合：

0, 3, 6, 7, 8

现在考虑一下您的代码运行情况，假设 k=4。

0, 3, 5, 9, 10

当 a[k]+1 等于 11 时，k 变成了 3。
当 ++a[k] 等于 10 时，a[k+1] 变成了 10，并且 k 变成了 4。
当 ++a[k] 等于 11 时，k 变成了 3。
当 ++a[k] 等于 11 时，k 变成了 2。
当 ++a[k] 等于 6 时，a[k+1] 变成了 6，并且 k 变成了 3。
当 ++a[k] 等于 7 时，a[k+1] 变成了 7，并且 k 变成了 4。
当 ++a[k] 等于 8 时，我们继续调用 print 函数。

这段代码是正确的，但不够高效，因为 k 在寻找可以递增而不会导致更高位数值溢出的最高索引时来回移动。实际上，如果最高索引从末尾算起是 j，则代码使用非线性次数的 while 循环迭代。您可以自行演示这一点，如果追踪当 n==dist 时不同值的 n 产生了多少次 while 循环迭代。虽然只有一行输出，但您将看到迭代次数呈 O(2^n) 增长（实际上，您将看到 2^(n+1)-2 次迭代）。

这种来回移动使您的代码变得低效，并且也难以分析。

相反，您可以以更直接的方式编写代码：

void hamming2(const char* num, size_t dist) {
    int a[dist];
    for (int i = 0; i < dist; i++) {
        a[i] = i;
    }
    size_t n = strlen(num);
    while (true) {
        print(num, a);
        int i;
        for (i = dist - 1; i >= 0; i--) {
            if (a[i] < n - dist + i) break;
        }
        if (i < 0) return;
        a[i]++;
        for (int j = i+1; j<dist; j++) a[j] = a[i] + j - i;
    }
}

现在，每次通过 while 循环产生一组新的索引。每次迭代的精确成本并不容易确定，但由于 print 是 O(n)，而 while 循环中剩余的代码最多是 O(dist)，因此总体成本为 O(N_INCR_SEQ(n, dist) * n)，其中 N_INCR_SEQ(n, dist) 是长度为 dist 的小于 n 的自然数递增序列的数量。评论区中有人提供了一个给出这个公式的链接。