這個算法在Big-O符號（字符串排列）中的順序是什麼？

以下算法的Big-O符號的性能如何？這是我寫的打印字符串的所有排列的函數。我知道輸入的長度爲n有n！不同的排列。有人可以提供解釋，以達到這樣的結論嗎？這個算法在Big-O符號（字符串排列）中的順序是什麼？

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

來源

2012-12-02 user1870756

對於最終的解釋看看克努特，卷4A：生成所有排列。 – cxxl

不要使用遞歸方法。嘗試轉換爲迭代。否則，你很快會面臨**堆棧溢出**。 –

@ shiplu.mokadd.im如果您使用尾遞歸函數，這無關緊要，因爲良好的編譯器可以優化這種情況。 – fuz

我要說爲O（n！），因爲每次遞歸做一個循環，其中n輪和「大小」的對象上調用一些N-1（因爲使用[我]已經屏蔽掉了一個字）。

來源

2012-12-02 18:12:30 cxxl

我知道輸入的長度爲n有n！不同的排列。

你剛纔已經回答你自己的問題

來源

2012-12-02 18:30:38 James

那麼，他的執行情況可能比O（n！）差。 :) – cxxl

它確實不是n !. N！只是實際完成排列並打印它的遞歸調用的數量，但不是所有的遞歸調用都這樣做。 – user1870756

n！是僅在最後一步中的呼叫數量。總呼叫次數爲：'n + n *（n-1）+ n *（n-1）*（n-2）+ ... n！' – acheron55

這個算法在Big-O符號（字符串排列）中的順序是什麼？

回答

相關問題