時間遞歸for循環代碼

我有這樣的代碼的複雜性，時間遞歸for循環代碼

void Generate(List<string> comb, string prefix, string remaining) 
{ 
     int currentDigit = Int32.Parse(remaining.Substring(0, 1)); 

      if (remaining.Length == 1) 
      { 
       for (int i = 0; i < dictionary[currentDigit].Length; i++) 
       { 
        comb.Add(prefix + dictionary[currentDigit][i]); 
       } 
      } 
      else 
      { 
       for (int i = 0; i < dictionary[currentDigit].Length; i++) 
       { 
        Generate(comb, prefix + dictionary[currentDigit][i], remaining.Substring(1)); 
       } 
      } 
}

什麼上面的代碼的時間複雜度？

它生成的是O（n），它本身正在執行n次，所以O（n^2）？

字典爲len = 10，並具有存儲其電話鍵盤英寸2 =「ABC」等

該代碼的初始呼叫將像

生成（新列表（）「」，「12345」）;

謝謝。

來源

2011-11-27 parsh

它似乎取決於'字典[currentDigit]'，沒有發佈。 –

'n'是什麼？剩餘的初始大小？我猜你的字典大小最多爲10。 –

發佈字典[大小]。僅供參考 - 此代碼來自SO中的答案，因此有興趣瞭解其時間複雜性。 – parsh

假設字典大小是m和輸入字符串的大小是n（剩餘），這將是：

T(1) = m + constant; 
T(n) = m T(n-1) + O(n) ==> T(n) = O(m^n)

實際上在else部分的每個正在運行時，將運行的m倍，O-的函數（n）的。

來源

2011-11-27 19:19:51

對不起，我忽略了這是遞歸方法 – sll

@ saeeda-amiri - 我沒有得到你的最後一句話，它是如何改變爲O（mn^n）？它不應該保持爲O（m^n） – parsh

@parsh是的，你是對的，我將首先編輯它，但如果你想評論某人，在他的回答或帖子中不需要使用'@' 。此外，如果這回答你的問題作爲答案。 –

時間遞歸for循環代碼

回答

相關問題