递归字符串排列函数的复杂度

Question

来自：有更好的字符串排列方法吗？

这个函数的时间复杂度是多少？

void permute(string elems, int mid, int end)
{
    static int count;
    if (mid == end) {
        cout << ++count << " : " << elems << endl;
        return ;
    }
    else {
    for (int i = mid; i <= end; i++) {
            swap(elems, mid, i);
            permute(elems, mid + 1, end);
            swap(elems, mid, i);
        }
    }
}

- rajya vardhan

Answer 1

忽略print函数后，满足的递归关系为：

T(n) = n*T(n-1) + O(n)

如果 G(n) = T(n)/n!，则有：

G(n) = G(n-1) + O(1/(n-1)!)

这意味着 G(n) = Theta(1)。

因此，T(n) = Theta(n!)。

假设print函数恰好执行了n！次，则时间复杂度为：

Theta(n * n!)。

- Aryabhatta

---

@rajyavardhan：为什么初始递归中有一个O(n)因子？ - crisron

由于交换操作 - 每个操作都需要O(1)，并且这发生在循环中。 - Parth Thakkar

由于存储在Set中的唯一排列随着初始输入的增加而变得更大，因此空间复杂度是否也是二次的O(n^2)？ - AdamHurwitz

Answer 2

不需要深入查看您的代码，我可以相当自信地说它的复杂度是O(n!)。这是因为任何有效的枚举n个不同元素的所有排列的过程都必须迭代每个排列。有n!种排列，因此算法至少需要O(n!)。

编辑：

实际上，这是O(n*n!)。感谢@templatetypedef指出这一点。

- MAK

---

我认为你忘记了打印O(n)个字符的O(n!)次，这需要O(n x n!)的时间。 - templatetypedef

@templatetypedef: n*n!<(n+1)n!, 即 nn!<(n+1)!。O((n+1)!) 和 O(n!) 是相同的，多出来的 n 并不重要。 - MAK

@MAK- O(n!) != O((n+1)!). 这句话的意思是，虽然任何O(n!)的函数都可以被视为O((n+1)!)的函数，但反过来不成立。快速证明方法如下：(n+1)! = O((n+1)!) 很显然。现在假设(n+1)! = O(n!)；那么就必须有一些c和n0，使得对于任何n > n0，(n+1)! < c n!。这将意味着对于任何n > n0，n < c，这对于任何常数c都是不可能的。 - templatetypedef

Answer 3

long long O(int n)
{
    if (n == 0)
        return 1;
    else 
       return 2 + n * O(n-1);
}

int main()
{
    //do something
    O(end - mid);
}

这将计算算法的复杂度。

实际上，O(N)是 N!!! = 1 * 3 * 6 * ... * 3N

- Mihran Hovsepyan