c - 该算法在 Big-O 表示法(字符串排列)中的顺序是什么？

Question

以下算法的大 O 表示法的性能如何？ 这是我编写的函数，用于打印字符串的所有排列。 我知道对于长度为 n 的输入有 n!不同的排列。 有人可以解释为得出这样的结论所做的分析吗？

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

void permute(char* output, char* input, int used[], int index, int length){
    int i;

    if (index == length) {
        printf("%s\n", output);
        return;
    }

    for (i=0; i< length; i++){
        if (! used[i] ){
            output[index] = input[i];
            used[i] = 1;
            permute(output, input, used, index+1, length);
            used[i] = 0;
        }
    }
}


int main(){
    char input[] = "abcd";
    char* output;
    int length = strlen(input);
    int* used;

    // Allocate space for used array
    used = (int*) malloc (sizeof (int)* length);
    memset (used, 0, sizeof (int)* length);

    // Allocate output buffer
    output = (char*) malloc ( length+1);
    if (!output) return 1;
    output[length] = '\0';

    // First recursive call
    permute(output, input, used, 0, length);

    free (output);

    return 0;
}

Answer 1

I know for an input of length n there are n! different permutations.

你刚刚回答了你自己的问题