Distinct Subsequencesの時間複雑度を計算する

Question

質問はleetcodeです。私は以下のコードを思いついたが、時間の複雑さを知るのは難しい。任意のアイデアはどのようにその時間の複雑さを計算する？ （どのような辞書メモリなしの場合）

 public int NumDistinct (string s, string t) 
     { 
      if (string.IsNullOrEmpty (s) && string.IsNullOrEmpty (t)) 
       return 1; 
      else if (string.IsNullOrEmpty (s) || string.IsNullOrEmpty (t)) 
       return 0; 

      return FindSequences (s, 0, t, 0); 
     } 

     Dictionary<string, int> memoery = new Dictionary<string, int>(); 

     private int FindSequences (string s, int idxs, string t, int idxt) 
     { 
      if (idxt == t.Length) 
       return 1; 
      else if (idxs == s.Length) 
       return 0; 

      string key = string.Format ("{0}-{1}", idxs, idxt); 
      if (memoery.ContainsKey (key)) 
       return memoery [key]; 

      int result = 0; 
      if (s [idxs] == t [idxt]) { 
       result = FindSequences (s, idxs + 1, t, idxt + 1) + FindSequences (s, idxs + 1, t, idxt); 
      } else { 
       result = FindSequences (s, idxs + 1, t, idxt); 
      } 
      memoery.Add (key, result); 
      return result; 
     } 

Answer 1

ここでの時間の複雑さはO(SizeOf(s) * SizeOf(t))です。 Dynamic Programming Solutionsの場合、異なる状態量を使用して時間複雑度を計算できます。ここでは状態量はSizeOf(s) * sizeOf(t)です。

ダイナミックプログラミングでは、同じ状態に遭遇したときに使用できるように状態の結果を格納するという概念を使用しているため、状態が頻繁に繰り返されたり、使用すると効果的に冗長な計算をしません結果は時間複雑度を下げるために計算されます。

：

はまた、あなたもDictionary Look upとDictionary Insertionの時間も考慮しなければならないので、時間の複雑さも、効果的にするために複雑になって、上記の場合にはDictionaryあるLook up tableまたはDP Tableに依存することに注意してください

O(SizeOf(s) * SizeOf(t) * Time to look Up or insert in Dictionary)。