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

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)

Если 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 различных элементов должна будет повторяться по каждой перестановке.Нет!перестановки, поэтому алгоритм должен быть не менее O (n!).

Edit:

Это на самом деле 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