algorithm - programa - complejidad de la función de permutación de cadena recursiva

permutar array java

Question

De: ¿Hay mejores métodos para hacer permutación de cadena?

¿Cuál es la complejidad de esta función?

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

Ignorando la impresión, la relación de recurrencia satisfecha es

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

Si G(n) = T(n)/n! obtenemos

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

lo que da G(n) = Theta(1) .

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

Suponiendo que la impresión sucede exactamente n! veces, obtenemos la complejidad del tiempo como

Theta(n * n!)

Answer 2

Sin mirar demasiado profundamente su código, creo que puedo decir con razonable confianza que su complejidad es O (n!). Esto se debe a que cualquier procedimiento eficiente para enumerar todas las permutaciones de n elementos distintos tendrá que iterar sobre cada permutación. ¡No hay! permutaciones, por lo que el algoritmo debe ser al menos O (n!).

Editar:

Esto es en realidad O (n * n!). Gracias a @templatetypedef por señalar esto.

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

Esto calculará la complejidad del algoritmo.

Actualmente O (N) es N!!! = 1 * 3 * 6 * ... * 3N N!!! = 1 * 3 * 6 * ... * 3N