algorithm - 计算不同子序列的时间复杂度

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))。对于动态编程解决方案，您可以使用您拥有的不同状态的数量来计算时间复杂度，这里的状态数量是SizeOf(s) * sizeOf(t) .

动态编程使用Memoisation 的概念，即存储状态的结果，以便在我们遇到相同状态时可以使用它，因此有效地我们不进行冗余计算，因为状态经常重复当他们这样做时，我们使用之前计算的结果来降低时间复杂度。

另请注意，时间复杂度还取决于 Look up table 或 DP Table，在上述情况下是 Dictionary，因此您还必须考虑 Dictionary Look up 和 Dictionary Insertion 的时间，有效地使复杂度为:

O(SizeOf(s) * SizeOf(t) * 查找或插入字典的时间)。