1

次のアルゴリズムの Big-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;
}
4

2 に答える 2

4

長さ n の入力には n があることを知っています! 異なる順列。

あなたはちょうどあなた自身の質問に答えました

于 2012-12-02T18:30:38.137 に答える
1

すべての再帰は n ラウンドのループを実行し、「サイズ」n-1 のオブジェクトで何かを呼び出すため (used[i] が 1 文字をマスクしているため)、O(n!) と言えます。

于 2012-12-02T18:12:30.070 に答える