这个计算向量笛卡尔积的函数的 time/space 复杂度是多少？

Question

我无法弄清楚此函数的时间和 space 复杂度。

vector<vector<string>> stringCombinations(const vector<vector<string>> &values) {
    vector<vector<string>> results = {{}};

    for(const auto &vec: values) {
        vector<vector<string>> temp;

        for(const auto &r: results) {
            for(const auto &s: vec) {
                temp.push_back(r);
                temp.back().push_back(s);
            }
        }

        results = move(temp);
    }

    for(const auto &row: results) {
        for(const auto &s: row) {
            cout << s << " ";
        }
        cout << endl;
    }

    return results;
}

这个函数只是字符串的笛卡尔积。给定一个字符串向量的向量，它打印 returns 这些字符串的所有组合。

当看到 3 个嵌套循环时，我立即认为它的时间复杂度大致在 O(n³) 的规模上。但是，随着函数的继续，第二个循环的长度发生变化运行。在第一次迭代中，向量中只有一个元素，即空向量。在第二次迭代中，它包含 n 个长度为 1 的向量，其中 n 是第一个字符串向量的长度。所以我真的不确定这会如何影响事情。

至于 space 复杂度，我认为它大约在 O(m*n) 左右，因为用于存储结果的 2D 向量。我只是不确定 m 和 n 到底是什么。

Answer 1

计算长度 k 的 n 个向量的笛卡尔积的 stringCombinations() 函数的复杂度是 O(n * k^n).

设v为函数stringCombinations()的参数，设n表示v.size()。设 v1 ... vn 表示 v 的元素并设 |u|表示向量中元素的数量 u.

该函数计算 n 向量的笛卡尔积 v1 ... vn .结果向量的大小 results 是 |v1| * |v2| * .... * |vn|。 results 的每个元素都是一个大小为 n 的向量。让 k 表示最大值（|v1|,..., |vn|）。

现在我们可以估计算法的复杂度了。令 f(i) 表示在第一个循环的 ith 迭代上第二个循环的迭代次数。然后我们将得到 O(n * f(n) * k) 作为 k是第三次循环迭代次数的上限。

对于f(n)，我们有以下公式。如果 ki 是 vi 中的字符串数，那么 f(i) = f(i-1) * k(i-1)。由于 f(1) = 1，很容易看出 f(n) = 1 * k1 * ... * k(n-1) = O(k^(n-1))。那么主循环的复杂度受限于 O(n * k^n).

13.03.2018更新让我们在这里详细介绍一下（并澄清符号并修复过程中的一些错误） .在第一个循环的每次迭代中，第二个循环遍历 results 向量。在第一次迭代中，它包含 1 个元素 {}。在第二次迭代中，results 的大小等于我们用 k1 表示的第一个元素 values 的大小。在 vec = {s1,s2,...} 的第二次迭代中，每个元素 r={s} 将被替换为 k2 元素。 {s,s1},{s,s2},..., 因此第二次迭代后 result 向量的大小将等于 k1 * k2。在每次后续迭代 i 之后，result 的大小将乘以 ki。这个大小将决定第二次循环在第一次循环的下一次迭代中的迭代次数。所以 *f(i+1) = 1 * k1 * ... * ki.

一个例子会很方便。让values = {{"1","2"},{"3","4","5"}}。这里 n = 2。在第一次迭代开始时我们有

   results = {{}}, vec={"1","2"}, *k1* = 2, *f(1)*=1

在第二次迭代开始时我们有

   results = {{"1"},{"2"}}, vec={"3","4","5"}, *k2*=3, *f(2)*=2

最后我们有

   results = {{"1","3"},{"1","4"},{"1","5"},
              {"2","3"},{"2","4"},{"2","5"}}

运算次数为T = f(1) * k1 + f(2) * k2。由于 k = max(k1,k2) = 3，我们有 T <=3 * (f(1) + f(2)) <= 3 * f (2)*2。 更新结束

另请注意，results中的元素数量受 O(n * k^n) 的限制，所以这也是第二个循环的复杂度。

正如你所说的那样，如果我们让 m = k^n，那么复杂度是 O( m * n)。然而，这种表示法可能会产生误导，因为输入数组可以被视为 n by k 数组，因此最好用以下术语给出复杂度估计输入数组的维度，所以它是 O(n * k^n).

这个计算向量笛卡尔积的函数的 time/space 复杂度是多少？

What is the time/space complexity of this function that calculates the cartesian product of vectors?

time-complexity

complexity-theory

asymptotic-complexity

space-complexity