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

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);
        }
    }
}

Answer 1

忽略打印​​，满足的递推关系是

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

If G(n) = T(n)/n! 我们得到

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

给出G(n) = Theta(1)。

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

假设打印恰好发生 n! 次，我们得到的时间复杂度为

Theta(n * n!)

Answer 2

在不深入研究您的代码的情况下，我想我可以有合理的信心地说它的复杂性是 O(n!)。这是因为任何枚举 n 个不同元素的所有排列的有效过程都必须迭代每个排列。有n个！排列，因此算法必须至少为 O(n!)。

编辑：

这实际上是 O(n*n!)。感谢@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