此代碼的時間複雜度列出所有排列？

例如，如果輸入字符串是「ABC」，則輸出應該是「ABC，ACB，BAC，BCA，CAB，CBA」。此代碼的時間複雜度列出所有排列？

這裏是我的方法：

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

void print(char str[],int visited[],int index,char temp[],int len) 
{ 



    if(index==len) 
    { 
     temp[index]='\0'; 
     printf("\n%s",temp); 
     return; 
    } 


    for(int i=0;i<len;i++) 
    { 
     if(!visited[str[i]-'A']) 
     { 
      visited[str[i]-'A']=1; 
      temp[index]=str[i]; 
      print(str,visited,index+1,temp,len); 
      visited[str[i]-'A']=0; 
     } 
    } 


} 

int main() 
{ 
    int visited[20]={0}; 
    char temp[20]; 
    char str[] = "ABCD"; 
    int len=strlen(str); 
    print(str,visited,0,temp,len); 

    getch(); 
    return 0; 
}

我已經使用訪問陣列，以避免字符的重複。這段代碼的複雜程度如何？

來源

2013-10-11 nikola

'std :: next_permutation'。 – Rapptz

@Rapptz我知道這個功能。但我想知道這段代碼的運行時間是多少。 – nikola

您確定要將其標記爲C++嗎？這對我來說看起來像C。 – Rapptz

如果讓n是可用字符的總數，並且k是尚未挑選的字符數，則可以看到每個函數調用確實工作Θ（n）（通過迭代長度爲len的數組或打印出一串長度爲len的字符串），然後生成k個遞歸調用。每次通話所完成的總工作總是Θ（n），所以我們可以通過查看總共撥打多少電話來計算完成的全部工作。

注意會有= N

1呼叫，其中k，
n次呼叫，其中k = N - 1，
N（N-1）K = N調用 - 2 ，
N（N-1）（N-2），其中k = N調用 - 3，
...
N！/k！呼叫了k

所以呼叫的總數由總和從K = 0到n

總和給出（N！/ K！）

= N！（總和從k = 0到n（1/k！））

一個有趣的觀察結果是這裏的總和是e（1/0！+ 1/1！+ 1/2！ + 1/3！+ ...），提前一點截斷。因此，隨着n變大，調用的數量漸近地接近e！！它的下界也是n !,所以這個總和是Θ（n！）。由於每次通話完成Θ（n）工作，因此完成的工作總量爲Θ（n＆middot; n！）。

希望這有助於！

來源

2013-10-11 20:33:14 templatetypedef

感謝這麼好的解釋！我也想問爲什麼的printf取O（n）的時間來打印一個字符串？ – nikola

@ user2549925-想想的時候每個字符發送到屏幕上所需的時間。你擁有的字符越多，需要更多的時間來顯示它們。 – templatetypedef

運行你的代碼和上市取決於字符串來排列的長度print()呼叫的數量，我已經得到了：「E * N」

n=1 calls=2 
n=2 calls=5 
n=3 calls=16 
n=4 calls=65 
n=5 calls=326 
n=6 calls=1957 
n=7 calls=13700 
n=8 calls=109601 
n=9 calls=986410 
n=10 calls=9864101 
n=11 calls=108505112

那樣子。

來源

2013-10-11 09:06:46

你有沒有嘗試重複字符的字符串？像aabbbccc？ –

不，我總是以排序的字母串開始，如「ABCDEF」。問題標題中提到「不重複」。 –

拜訪陣列是用於這一目的，我覺得:)我猜測，沒有重複在這裏的意思是沒有字符串出現兩次:) –

此代碼的時間複雜度列出所有排列？

回答

相關問題