递归串置换功能的复杂性 [英] complexity of recursive string permutation function

问题描述

从：<一href="http://stackoverflow.com/questions/1995328/are-there-any-better-methods-to-do-permutation-of-string">Are有没有更好的方法做字符串置换？

什么是这个函数???

的复杂性

 无效置换（字符串elems，诠释中期，诠释完）
{
    静态诠释计数;
    如果（==中旬结束）{
        COUT＆LT;＆LT; ++计数＆LT;＆LT; ：＆其中;＆其中; elems＆LT;＆LT; ENDL;
        返回 ;
    }
    其他 {
    的for（int i =中间; I＆LT; =结束;我++）{
            掉期（elems，中，I）;
            置换（elems，中+ 1，结束）;
            掉期（elems，中，I）;
        }
    }
}
 

解决方案

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

T（N）= N * T（N-1）+ O（N）

如果 G（N）= T（N）/ N！我们得到

G（N）= G（N-1）+ O（1 /（N-1）！）

这使得 G（N）=西塔（1）。

因此​​ T（N）=西塔（N！）。

假设打印的情况完全相同 N！的时候，我们得到的时间复杂度为

的Theta（N * N！）

From: Are there any better methods to do permutation of string?

what is the complexity of this function???

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

解决方案

Ignoring the print, the recurrence relation satisfied is

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

If G(n) = T(n)/n! we get

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

which gives G(n) = Theta(1).

Thus T(n) = Theta(n!).

Assuming that the print happens exactly n! times, we get the time complexity as

Theta(n * n!)

这篇关于递归串置换功能的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！