Permutationen einer String-Algorithmus-Analyse

Question

Ich habe zwei Algorithmen zum Drucken der Permutationen einer Zeichenfolge

Hier ist die erste.

#include<iostream> 

int fact(int f) 
{ 
    if(f == 0) 
     return 1; 
    return f*fact(f-1); 
} 
int main() 
{ 
    char A[] = "abc"; 
    int size = strlen(A); 
    int per = fact(size); // per is the number of permutations we will get 

    int j = 0; // j is the index of the elements of A we will swap 

    // this is the algorithm 
    for(int i=1;i<=per;i++) 
    { 
     cout << A << endl; 
     if(j == size-1) 
     j = 0; 
     swap(A[j],A[j+1]); 
     j++; 
    } 

    return 0; 
} 

Hier ist der zweite.

// C program to print all permutations of the input string 

#include <stdio.h> 
#include <string.h> 

// Function to swap values at two pointers 
void swap(char *x, char *y) 
{  
    char temp = *x; 
    *x = *y; 
    *y = temp; 
} 

// Function to print permutations of string 
This function takes three parameters: 
1. String 
2. Starting index of the string or sub-string 
3. Ending index of the string 

void permute(char *a, int l, int r) 
{ 
    int i; 
    if (l == r) 
    printf("%s\n", a); 
    else 
    { 
    for(i = l; i <= r; i++) 
    { 
     swap((a+l), (a+i)); 
     permute(a, l+1, r); 
     swap((a+l), (a+i)); //backtrack to retain the original string 
    } 
    } 
} 

int main() 
{ 
    char str[50]; 

    gets_s(str); 

    int n = strlen(str); 
    permute(str, 0, n-1); 

    return 0; 
} 

ich nach ... beide sollen das gleiche ausführen .... und sie in der Tat tun .... aber nur für kleinen inputs..eg: „abc“, „ABCD“ .Aber wenn die Saite wird groß..eg: "abcdefghi" .. der erste nimmt verdammt viel Zeit in Anspruch, im Gegensatz zum zweiten.

Ich habe eine harte Zeit zu analysieren, warum der zweite besser als der erste führt. Kann mir jemand dies erklären?

Answer 1

Direkt unter Anweisung in Ihnen Hauptfunktion hinzufügen, bevor Sie den Druckvorgang starten:

std::cout.sync_with_stdio(false); 

Dies deaktiviert die Synchronisation mit dem Standard C-streams für jeden IO-Betrieb.

Lesen Sie mehr darüber here