Сложность рекурсивной функции перестановки строк

От: Есть ли какие-нибудь лучшие методы для перестановки строки?

Какова сложность этой функции???

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

Ответы

Ответ 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!)

Ответ 2

Не задумываясь над своим кодом, я могу с уверенностью сказать, что его сложность - O (n!). Это связано с тем, что любая эффективная процедура для перечисления всех перестановок из n отдельных элементов должна будет перебираться по каждой перестановке. Нет! перестановки, поэтому алгоритм должен быть как минимум O (n!).

Edit:

Это на самом деле O (n * n!). Благодаря @templatetypedef для указания этого.

Ответ 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);
}

Это вычислит сложность алгоритма.

Actualy O (N) - N!!! = 1 * 3 * 6 * ... * 3N