java - 这段代码的时间复杂度o()是多少？ java

Question

我认为是 O(3^n)，有什么想法吗？ 此方法查找给定数字是否是给定集合的任何子集的总和(overoads boolean isSumOf(int [] s，int n))。 如果 taget 等于 0 或消耗集合中的当前数字(或不消耗)并再次尝试，则该方法会在每次递归调用中检查， while target>0 并且我们还没有耗尽数组。

    * @param set a given set of natural numbers.
    * @param target the number. 
    * @param i where we are in the set.
    * @return true if we reached target, else returns false.
    **/
   private static boolean isSumOf(int[] set,int target,int i)
   {

        // Found the set if we are now at 0.
        boolean isSum = (target==0);
        // Look no further if no more to try.
        if ( target > 0 ) 
        {
            // Look no further if we've exhausted the array.
            if ( i < set.length )
            {
                // Try or consume this number in the set (or not) and try again.
                isSum = isSumOf(set, target - set[i], i)  // Consume the current number in the set and try again recursively. 
                    || isSumOf(set, target - set[i], i+1) // Consume the current number in the set and avdance to rhe next number.
                    || isSumOf(set, target, i+1); // Try the current number and avance to the next number in the set.
            }

        }

        return isSum;

Answer 1

您的问题是 NP 完全问题。这些都是坏消息。

好消息是这是一个众所周知的 NP 完全问题!是的!

http://en.wikipedia.org/wiki/Subset_sum

正如评论中所说，您的算法可以无限期运行，并且即使输入大小适中也可以运行很长时间。

如果您希望该代码在中等大小的输入中运行，您需要重新考虑您的方法。

您的方法中的一个大问题是您正在计算许多重复的子问题。想想通常的朴素斐波那契递归实现。

从好的方面来说，您的子问题具有相当理想的结构，这很好地表明您的问题非常适合动态规划方法。它使事情变得更简单，您甚至不需要总和为该值的确切数字，只需一个 boolean 输出。

我链接的维基百科文章讨论了一些伪多项式方法以及通过动态规划的多项式方法。