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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了这段代码的时间复杂度o()是多少？ java的，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1690字，纯文字阅读大概需要3分钟。

内容图文

我认为是O(3 ^ n),任何想法？
     此方法查找给定数字是否是给定集合的任何子集合的总和(overoads boolean isSumOf(int [] s,int n)).
     如果taget等于0或者消耗集合中的当前数字(或不消耗)并再次尝试,则该方法在每次递归调用中都会查询,
     目标> 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;

解决方法:

你的问题是NP完全的.这些都是坏消息.

好消息是,这是一个非常着名的NP完全问题！ Yey！

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

就像在评论中所说的那样,你的算法可以无限期地运行,并且即使是适度的输入大小也会运行很长时间.

如果您对该代码在中等大小的输入中运行有任何希望,您需要重新考虑您的方法.

您的方法中的一个主要问题是您正在计算许多重复的子问题.想想通常天真的Fibonnaci递归实现.

你的子问题,在光明的一面,有一个非常优化的结构,这是一个很好的指标,你的问题将是动态编程方法的一个很好的候选人.它使事情变得更容易,你甚至不需要总结到值的确切数字,只是一个布尔输出.

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

内容总结

以上是互联网集市为您收集整理的这段代码的时间复杂度o()是多少？ java的全部内容，希望文章能够帮你解决这段代码的时间复杂度o()是多少？ java的所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端