递归字符串置换函数的复杂性

Question

From:有没有更好的方法来排列字符串？

这个功能的复杂性是什么？

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)

如果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指出这一点.